Bekannteste Joint Containments für / von NP und Parity-P?

18

Parity-P ist die Menge von Sprachen, die von einer nicht-deterministischen Turing-Maschine erkannt werden und die nur zwischen einer geraden oder ungeraden Anzahl von "Akzeptanz" -Pfaden unterscheiden kann (anstelle einer Null- oder einer Nicht-Null-Anzahl von Akzeptanzpfaden). So Parity-P ist im Grunde PP ‚s verkrüppelte jüngere Geschwister: während PP zählt , ob die Anzahl der Annahme Wege eines NP-Maschine eine Mehrheit ist oder nicht ( dh die höchstwertigen Bits dieser Menge), Parity-P zeigt das niedrigstwertige Bit der Anzahl der akzeptierenden Pfade.

Wie NP enthält Parity-P UP (was P "wahrscheinlich" genau so enthält); und wie NP ist Parity-P in PSPACE enthalten.

Frage. Was sind die bekanntesten Gelenkober- und -untergrenzen für NP und Parity-P?

cc.complexity-theory complexity-classes np Niel de Beaudrap
quelle

Antworten:

17

Nach Valiant-Vazirani ist NP im BP-Punkt Parity-P enthalten (der offensichtlich Parity-P enthält). Darüber hinaus zeigte Toda, dass PH in BP-Punktparität-P ist, was in P ^ (# P) ist (was in PSPACE ist).

Für untere Schranken denke ich, dass beide Klassen eine Klasse enthalten, die als FewP bekannt ist und UP enthält und wie NP ist, aber Sie fragen, dass Zeichenketten in der Sprache höchstens polynomiell viele akzeptierende Pfade haben.

[Update: korrigierter Tippfehler BPP statt BP]

Manu
quelle
5
Eine Folge des Einschlusses PH im BPP-Punkt Parität-P ist, dass Parität-P nicht in der Polyhierarchie enthalten ist, es sei denn, diese Hierarchie kollabiert.
Andy Drucker
4
Dies folgt, weil dann, wenn Parität-P in Sigma_k-P ist, PH in BPP-Punkt Sigma_k-P ist, der in Pi_ (k + 1) -P enthalten ist. (Diese letzte Eingrenzung ergibt sich aus einer einfachen Verallgemeinerung des Operators des Ergebnisses, dass BPP in Sigma_2 P Pi_2 P schneidet.)
Andy Drucker
4
Ich halte es für plausibel, dass der BPP-Punkt Parity-P in P ^ (Parity-P) enthalten ist. Wenn dies wahr ist, dann ist PH in P ^ (Parität) enthalten, das in (Parität-P) ^ (Parität-P) enthalten ist, was tatsächlich Parität-P entspricht. Was ich nicht sicher bin, ist, ob irgendwelche Arbeiten über Härte gegen Zufälligkeit eine Hypothese ergeben, die den in P ^ (Parität-P) enthaltenen BPP-Punkt Parität-P impliziert.
Andy Drucker
4
Schließlich unterscheidet sich Parity-P von NP- und anderen PH-Klassen dadurch, dass bekannt ist, dass es Reduktionen von Worst-Case zu Average-Case aufweist. Das heißt, wenn Parity-P nicht in P ist, enthält es Verteilungsprobleme, die im Durchschnitt schwer sind. Siehe Feigenbaum-Fortnow, "Zufällige Selbstreduzierbarkeit vollständiger Mengen".
Andy Drucker
3
Hier ist die allgemeine Idee: Sei C eine Komplexitätsklasse. Eine Sprache L ist in (BPP Punkt C), wenn es eine Sprache S in C gibt, die aus codierten Paaren (x, r) besteht, so dass: -wenn x in L ist, dann für 2/3 von allen r das Paar (x, r) ist in S; -wenn x nicht in L ist, dann ist für 2/3 von r das Paar (x, r) nicht in S. (Technisch hängt die Länge von r von x ab und muss höchstens ein Polynom in | sein x |.)
Andy Drucker