Parita P - Parity P

v teorie výpočetní složitosti, třída složitosti ⊕P (vyslovuje se „parita P“) je třída rozhodovací problémy řešitelný a nedeterministický Turingův stroj v polynomiálním čase, kde podmínkou přijetí je, že počet akceptujících výpočetních cest je lichý. Příklad ⊕P problém je "má daný graf lichý počet perfektní párování ? “Třídu definovali Papadimitriou a Zachos v roce 1983.[1]

⊕P je počítací třída a lze ji považovat za nalezení nejméně významného bitu odpovědi na odpovídající #P problém. Problém najít nejvýznamnější bit je v PP. PP je považována za podstatně tvrdší třídu než ⊕P; například existuje relativizovaný vesmír (viz věštecký stroj ) kde P = ⊕P ≠ NP = PP = EXPTIME, jak ukazují Beigel, Buhrman a Fortnow v roce 1998.[2]

Zatímco Todova věta ukázat to PPP obsahuje PH, P⊕P není známo, že dokonce obsahuje NP. První část důkazu Todovy věty to však ukazuje BPP⊕P obsahuje PH. Lance Fortnow napsal výstižný důkaz této věty.[3]

⊕P obsahuje problém grafového izomorfismu a ve skutečnosti tento problém je nízký pro ⊕P.[4] Také to triviálně obsahuje NAHORU, protože všechny problémy v NAHORU mít buď nulu, nebo jednu přijímající cestu. Obecněji ⊕P je nízký pro sebe, což znamená, že takový stroj nezíská žádnou moc tím, že bude schopen vyřešit jakýkoli ⊕P problém okamžitě.

Symbol in v názvu třídy může být odkazem na použití symbolu ⊕ v Booleova algebra odkázat výlučná disjunkce operátor. To dává smysl, protože pokud považujeme „přijímá“ za 1 a „nepřijímá“ za 0, výsledkem stroje je výlučná disjunkce výsledků každé výpočetní cesty.

Reference

  1. ^ C. H. Papadimitriou a S. Zachos. Dvě poznámky k síle počítání. v Sborník ze 6. konference GI v teoretické informatice, Přednášky z informatiky, svazek 145, Springer-Verlag, str. 269–276. 1983.
  2. ^ R. Beigel, H. Buhrman a L. Fortnow. NP nemusí být tak snadné jako detekce jedinečných řešení. v Sborník ACM STOC'98, str. 203–208. 1998.
  3. ^ Fortnow, Lance (2009), „Jednoduchý důkaz Todovy věty“, Teorie výpočtu, 5: 135–140, doi:10.4086 / toc.2009.v005a007
  4. ^ Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), „Grafový izomorfismus je pro PP nízký“, Výpočetní složitost, 2 (4): 301–330, doi:10.1007 / BF01200427.