Czy Parity-P jest zawarty w PP?

To pytanie zadał Jan Pax na liście mailingowej Podstawy matematyki . Z pewnością ale z odpowiedzi na to pytanie podejrzewam , że nie wiadomo, czy (inaczej byłaby jedną z możliwych odpowiedzi na to pytanie). Jeśli nie wiadomo, czy istnieje separacja wyroczni? $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$ $\oplus P \subseteq PP$ $PP$

cc.complexity-theory complexity-classes Timothy Chow
źródło

Wikipedia mówi, że istnieje wyrocznia, dla której

( R. Beigel, H. Buhrman i L. Fortnow. NP może nie być tak łatwe jako wykrywanie unikalnych rozwiązań )

P^{A} = \oplus P^{A} \neq N P^{A} (= P P^{A}) = E X P^{A}

$P^A = \oplus P^A \neq NP^A ( = PP^A) = EXP^A$

Marzio De Biasi

Dzięki, Marzio. Chyba powinienem był powiedzieć bardziej konkretnie: czy istnieje wyrocznia

taka, że

A

$A$

\oplus P^{A} ⊈ P P^{A}

$\oplus P^A \not\subseteq PP^A$

Timothy Chow

To, co powiem, zawiera inne odpowiedzi, ale może być przydatne, jeśli chcesz uprościć sprawę. Wyrocznia, której szukasz, to po prostu zastosowanie znanego od dawna faktu, że perceptron nie może obliczyć PARYTETU (Minsky i Papert).

Alessandro Cosentino

@AlessandroCosentino Czy

? Co jeśli

były prawdziwe?

P P^{\oplus P} = P P

$PP^{\oplus P}=PP$

{\oplus P}^{P P} = P P

${\oplus P}^{PP}=PP$

P P \subseteq \oplus P

$PP\subseteq\oplus P$

T ....

Odpowiedzi:

Tak, jest wyrocznią takie, że . W rzeczywistości nie jest wyrocznią tak, że . Możesz znaleźć wynik w poniższej pracy. $A$ $\oplus P^A \not\subseteq PP^A$ $A$ $\oplus P^A \not\subseteq PP^{PH^A}$

Frederic Green, Wyrocznia oddzielająca od , Listy przetwarzania informacji, Tom 37, Numer 3, 18 lutego 1991 r., Strony 149-153 $\oplus P$ $PP^{PH}$

Robin Kothari
źródło

Dzięki ... właśnie tego szukałem! W komentarzach na początku do swojego artykułu Green przypisuje doktorat Jacobo Torána. Praca z pierwszym oracle

tak, że

. Wynik ten został następnie opublikowany jako Twierdzenie 5.13 w pracy Torána „Klasy złożoności zdefiniowane przez zliczanie kwantyfikatorów”, JACM 38 (1991), 752–773.

A

$A$

\oplus P^{A} ⊈ P P^{A}

$\oplus P^A \not\subseteq PP^A$

Timothy Chow

Scott Aaronson daje wyrocznię, gdzie P = PEXP, co oznacza wyrocznię, którą chcesz. http://eccc.hpi-web.de/report/2005/040/download/ (Twierdzenie 12 w dodatku) $\oplus$

Lance Fortnow
źródło

Dzięki. Muszę wybrać tylko jedną odpowiedź do zaakceptowania, więc wybieram odpowiedź Robin Kothari, ponieważ jest to wcześniejsze odniesienie.

Timothy Chow