La parité-P est-elle contenue dans PP?

Cette question a été posée par Jan Pax sur la liste de diffusion Foundations of Mathematics . Certainement mais je soupçonne d'après les réponses à cette question que l'on ne sait pas si (sinon, serait une réponse possible à cette question). Si ce n'est pas connu, y a-t-il une séparation Oracle? $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$ $\oplus P \subseteq PP$ $PP$

cc.complexity-theory complexity-classes Timothy Chow
la source

Wikipedia dit qu'il y a un oracle pour lequel

( R. Beigel, H. Buhrman et L. Fortnow. NP pourrait ne pas être aussi facile comme détection de solutions uniques )

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

Merci, Marzio. Je suppose que j'aurais dû être plus précis: y a-t-il un oracle

tel que

A

$A$

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

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

Timothy Chow

Ce que je vais dire est résumé par les autres réponses, mais peut être utile si vous voulez garder les choses simples. L'oracle que vous recherchez n'est qu'une application du vieux fait connu qu'un perceptron ne peut pas calculer la PARITÉ (Minsky & Papert).

Alessandro Cosentino

@AlessandroCosentino Est-ce que

? Et si

était vrai?

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 ....

Réponses:

Oui, il y a un oracle tel que . En fait, il existe un oracle de telle sorte que . Vous pouvez trouver le résultat dans l'article suivant. $A$ $\oplus P^A \not\subseteq PP^A$ $A$ $\oplus P^A \not\subseteq PP^{PH^A}$

Frederic Green, Un oracle séparant de , Lettres de traitement de l'information, Volume 37, Numéro 3, 18 février 1991, Pages 149-153 $\oplus P$ $PP^{PH}$

Robin Kothari
la source

Merci ... c'est exactement ce que je cherchais! Dans les commentaires d'ouverture de son article, Green attribue le doctorat de Jacobo Torán. thèse avec le premier oracle

de telle sorte que

. Ce résultat a ensuite été publié sous le nom de Théorème 5.13 dans l'article de Torán «Classes de complexité définies par des quantificateurs de comptage», JACM 38 (1991), 752–773.

A

$A$

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

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

Timothy Chow

Scott Aaronson donne un oracle où P = PEXP qui implique l'oracle que vous voulez. http://eccc.hpi-web.de/report/2005/040/download/ (Théorème 12 en annexe) $\oplus$

Lance Fortnow
la source

Merci. Je dois choisir une seule réponse pour accepter, donc je choisis la réponse de Robin Kothari parce que c'est une référence antérieure.

Timothy Chow