Parität p

Im Computerkomplexitätstheorie, das Komplexitätsklasse ⊕P (ausgesprochen "Parität P") ist die Klasse von Entscheidungsprobleme lösbar durch a Nichtdeterministische Turing -Maschine In der Polynomzeit, in der die Akzeptanzbedingung lautet, dass die Anzahl der Annahme von Berechnungspfaden ungerade ist. Ein Beispiel für ein ⊕P Problem ist "hat eine bestimmte Grafik eine ungerade Anzahl von Perfekte Matchings? "Die Klasse wurde 1983 von Papadimitriou und Zachos definiert.[1]

⊕P ist eine Zählklasse und kann als das am wenigsten signifikante Stück der Antwort auf die entsprechende Förderung angesehen werden #P Problem. Das Problem, das bedeutendste Bit zu finden, ist in Pp. Pp Es wird angenommen, dass es eine wesentlich härtere Klasse ist als ⊕P; Zum Beispiel gibt es ein relativisiertes Universum (siehe Oracle Machine) wo P = ⊕P ≠ Np = Pp = Nachfolger, wie von Beigel, Buhrman und Fortnow im Jahr 1998 gezeigt.[2]

Während Todas Satz zeigt, dass PPp enthält PH, P⊕P Es ist nicht bekannt, dass er nicht einmal enthält Np. Der erste Teil des Beweises des Todas Theorems zeigt jedoch, dass dies der Fall ist BPP⊕P enthält PH. Lance Fortnow hat einen präzisen Beweis für diesen Satz geschrieben.[3]

⊕P enthält die Graph Isomorphismus Problemund in der Tat ist dieses Problem niedrig für ⊕P.[4] Es enthält auch trivial HOCHda alle Probleme in HOCH haben entweder Null oder einen Akzeptieren von Pfaden. Allgemeiner ⊕ ⊕P ist niedrig Für sich selbst, was bedeutet, dass eine solche Maschine keine Leistung erhält, wenn man in der Lage ist, irgendein ⊕ zu lösenP Problem sofort.

Das ⊕ -Symbol im Namen der Klasse kann ein Hinweis auf die Verwendung des Symbols ⊕ in sein boolsche Algebra um die zu verweisen Exklusive Disjunktion Operator. Dies ist sinnvoll, weil wir als "akzeptiert" als 1 und "nicht akzeptiert" als 0 angesehen werden, das Ergebnis der Maschine ist die ausschließliche Disjunktion der Ergebnisse jedes Berechnungspfads.

Externe Links

Verweise

  1. ^ C. H. Papadimitriou und S. Zachos. Zwei Bemerkungen zur Zählkraft. Im Verfahren der 6. GI -Konferenz in theoretischer Informatik, Vorlesungsnotizen in Informatik, Volume 145, Springer-Verlag, S. 269–276. 1983.
  2. ^ R. Beigel, H. Buhrman und L. Fortnow. Np Möglicherweise ist nicht so einfach wie die Erkennung von einzigartigen Lösungen. Im Verfahren von ACM STOC'98, S. 203–208. 1998.
  3. ^ Fortnow, Lance (2009), "Ein einfacher Beweis für Todas Theorem", Theorie des Computers, 5: 135–140, doi:10.4086/toc.2009.v005a007
  4. ^ Köter, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graph Isomorphismus ist für PP niedrig", Rechenkomplexität, 2 (4): 301–330, doi:10.1007/bf01200427.