Osvědčení (složitost) - Certificate (complexity)

v teorie výpočetní složitosti, a osvědčení (také nazývaný a svědek) je řetězec, který potvrzuje odpověď na výpočet, nebo potvrzuje členství v nějakém řetězci v jazyce. Certifikát je často považován za cestu řešení v rámci procesu ověřování, který se používá ke kontrole, zda problém dává odpověď „Ano“ nebo „Ne“.

V model rozhodovacího stromu výpočtu je složitost certifikátu minimálním počtem vstupní proměnné a rozhodovací strom které je třeba přiřadit hodnotu, aby bylo možné definitivně stanovit hodnotu Booleovská funkce .

Použít v definicích

K definici se používá pojem certifikát polorozhodnutelnost:[1] L je semi-rozhodnutelný, pokud existuje dvoumístný predikát R ⊆ Σ ∗ × Σ ∗ takový, že R je vypočítatelný, a takový, že pro všechna x ∈ Σ ∗:

   x ∈ L ⇔ existuje y takové, že R (x, y)

Certifikáty také poskytují definice pro některé třídy složitosti, které lze alternativně charakterizovat z hlediska nedeterministické Turingovy stroje. Jazyk L je v NP právě když existuje polynom str a a polynomiální čas ohraničený Turingův stroj M taková, že každé slovo X je v jazyce L přesně pokud existuje certifikát C maximálně délky p (| x |) takhle M přijímá pár (X, C).[2] Třída co-NP má podobnou definici, kromě toho, že pro tato slova existují certifikáty ne v jazyce.

Třída NL má definici certifikátu: problém v jazyce má certifikát polynomiální délky, který lze ověřit deterministickým Turingovým strojem ohraničeným logaritmickým prostorem, který dokáže přečíst každý bit certifikátu pouze jednou.[3]

Příklady

Problém stanovení pro daný graf G a číslo k, pokud graf obsahuje nezávislá sada velikosti k je v NP. Vzhledem k dvojici (G, k) v jazyce je certifikát sadou k vrcholy, které nejsou párově sousedící (a tudíž jsou nezávislou množinou velikostí k).[4]

Obecnější příklad problému stanovení, zda daný Turingův stroj přijímá vstup v určitém počtu kroků, je následující:

 L = {<, x, w> | přijímá  x v | w | kroky?} Zobrazit L ∈ NP. ověřovatel:   dostane řetězec c = , x, w takový, že | c | <= P (| w |) zkontrolujte, zda je c akceptující výpočet M na x s maximálně | w | kroky | c | <= O (| w |3) máme-li výpočet TM s k kroky, celková velikost výpočetního řetězce je k2   Tedy <, x, w> ∈ L ⇔ existuje c <= a | w |3 takové, že <, x, w, c> ∈ V ∈ P

Viz také

Reference

  1. ^ Cook, Stephen. „Vyčíslitelnost a nepočítatelnost“ (PDF). Citováno 7. února 2013.
  2. ^ Arora, Sanjeev; Barak, Boaz (2009). „Definice 2.1“. Teorie složitosti: moderní přístup. Cambridge University Press. ISBN  978-0-521-42426-4.
  3. ^ Arora, Sanjeev; Barak, Boaz (2009). "Definice 4.19". Teorie složitosti: moderní přístup. Cambridge University Press. ISBN  978-0-521-42426-4.
  4. ^ Arora, Sanjeev; Barak, Boaz (2009). „Příklad 2.2“. Teorie složitosti: moderní přístup. Cambridge University Press. ISBN  978-0-521-42426-4.

externí odkazy