Najbardziej znane wspólne pojemniki dla / przez NP i Parity-P?

18

Parzystość-P jest zbiorem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko parzystą liczbę lub nieparzystą liczbę ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji). Zatem Parity-P jest w zasadzie PP „s karłowate młodsze rodzeństwo: podczas liczy PP czy liczba przyjmujących ścieżkach NP-maszyna jest większość, czy nie ( czyli najczęściej znaczący bit tej ilości), Parity-P oznacza najmniej znaczący bit liczby ścieżek akceptujących.

Podobnie jak NP, parzystość-P zawiera UP (który zawiera P, „prawdopodobnie” ściśle tak); i podobnie jak NP, parzystość-P jest zawarta w PSPACE.

Pytanie. Jakie są najbardziej znane wspólne górne i dolne granice dla NP i parzystości-P?

cc.complexity-theory complexity-classes np Niel de Beaudrap
źródło

Odpowiedzi:

17

Według Valiant-Vazirani NP znajduje się w kropce BP Parity-P (która oczywiście zawiera Parity-P). Co więcej, Toda wykazał, że PH jest w parzystości BP kropki Parzystość-P, która jest w P ^ (# P) (która jest w PSPACE).

W przypadku dolnych granic, myślę, że obie klasy zawierają klasę znaną jako FewP, która zawiera UP i jest jak NP, ale pytacie, czy łańcuchy w języku mają co najwyżej wielomianowo wiele ścieżek akceptujących.

[Aktualizacja: poprawiono literówkę BPP zamiast BP]

Manu
źródło
5
Następstwem ograniczania PH w kropce BPP Parity-P jest to, że parzystość-P nie jest zawarta w wielowierszości, chyba że ta hierarchia się załamie.
Andy Drucker
4
Wynika to z tego, że jeśli parzystość-P jest w Sigma_k-P, to PH znajduje się w kropce BPP Sigma_k-P, która jest zawarta w Pi_ (k + 1) -P. (to ostatnie ograniczenie wynika z prostego uogólnienia „operatora” wyniku, że BPP jest w Sigma_2 P przecina Pi_2 P.)
Andy Drucker
4
Myślę, że uważa się za prawdopodobne, że kropka BPP Parity-P jest zawarta w P ^ (Parity-P). Jeśli jest to prawda, wówczas PH jest zawarte w P ^ (parzystość), która jest zawarta w (Parzystość-P) ^ (Parzystość-P), która faktycznie równa się Parzystości-P. Nie jestem pewien, czy jakiekolwiek dokumenty dotyczące twardości vs. losowości dają hipotezę, która implikuje kropkę BPP Parity-P zawartą w P ^ (Parity-P).
Andy Drucker,
4
Wreszcie, parzystość-P różni się od NP i innych klas PH tym, że wiadomo, że ma redukcje od najgorszych do średnich przypadków. Oznacza to, że jeśli parzystości-P nie ma w P, to zawiera problemy dystrybucyjne, które są trudne w średniej wielkości. Patrz Feigenbaum-Fortnow, „Losowa samoredukowalność kompletów”.
Andy Drucker,
3
Oto ogólna idea: niech C będzie klasą złożoności. Język L jest w (kropka C BPP), jeśli istnieje język S w C, składający się z zakodowanych par (x, r), taki że: -jeśli x jest w L, to dla 2/3 wszystkich r para (x, r) jest w S; -jeśli x nie jest w L, to dla 2/3 wszystkich r para (x, r) nie jest w S. (Technicznie długość r zależy od x i musi być co najwyżej jakąś wielomianem w | x |.)
Andy Drucker