Conséquences de

Je partie d'une tentative de preuve . La tentative de preuve consiste en une réduction Karp du problème -complete 3 RÉGULIER COUVERTURE vertex SAT. $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P}$ $\oplus$

Étant donné un graphique cubique , la réduction produit une formule CNF ayant les deux propriétés suivantes: $G$ $F$

a au plus affectation satisfaisante. $F$ $1$
$F$ est satisfiable si et seulement si le nombre de couvertures de sommets de $G$ est impair.

Des questions

Quelles seraient les conséquences de $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? Une conséquence que je connais déjà est la suivante: $\mathbf{PH}$ serait réductible à $\mathbf{NP}$ via une réduction randomisée bilatérale. En d'autres termes, nous aurions $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ (en utilisant le théorème de Toda, qui déclare que $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$ , en remplaçant simplement $\oplus\mathbf{P}$ par $\mathbf{NP}$ ). Je ne sais pas si $\mathbf{BPP}^{\mathbf{NP}}$ s'est avéré être contenu dans un certain niveau de la hiérarchie polynomiale: si oui, une autre conséquence serait que s'effondre à un tel niveau . ~~De plus, selon des hypothèses de dérandomisation largement acceptées (~~ ~~), la hiérarchie polynomiale s'effondrerait entre le premier et le deuxième niveau, car nous aurions~~ ~~(on me dit que ce n'est pas vrai, cependant je n'effacerai pas cette ligne jusqu'à ce que je comprenne bien pourquoi).~~ $i$ $\mathbf{PH}$ $i$ ~~$\mathbf{BPP} = \mathbf{P}$ $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta_2^\mathbf{P}$~~

$\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$ , ni dans quelle mesure. Intuitivement, je suppose que oui, et dans une large mesure.

cc.complexity-theory graph-theory complexity-classes sat counting-complexity Giorgio Camerani
la source

\oplus P

$\oplus\mathrm P$

\oplus P

$\oplus\mathrm P$

\oplus P \subseteq N P

$\oplus\mathrm P\subseteq\mathrm{NP}$

P H = Σ_{2}^{P} = Π_{2}^{P} = A M \cap c o A M

$\mathrm{PH}=\Sigma^P_2=\Pi^P_2=\mathrm{AM}\cap\mathrm{coAM}$

P H \subseteq N P / p o l y \cap c o N P / p o l y

$\mathrm{PH}\subseteq\mathrm{NP/poly}\cap\mathrm{coNP/poly}$ . UP ne fait pas beaucoup de différence (cf. le manque de tout ce qui est utile dans cstheory.stackexchange.com/questions/3887 ).

Emil Jeřábek

\oplus P \subseteq U P

$\oplus \mathbf{P}\subseteq\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

U P

$\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

{N P}^{A} = P^{A}

$\mathrm{NP}^A=\mathrm P^A$

A

$A$

N P \neq P

$\mathrm{NP}\ne\mathrm P$

B P P \neq P

$\mathrm{BPP}\ne\mathrm P$

A

$A$

{B P P}^{A} \neq P^{A}

$\mathrm{BPP}^A\ne\mathrm P^A$ .

Emil Jeřábek, le

@Giorgio: Il prétend seulement que le raisonnement que vous avez envisagé ne fonctionne pas dans ces circonstances. Portion pertinente: "Si la machine à laquelle j'attache l'oracle est au moins aussi puissante, pourquoi l'inclusion ne devrait-elle pas suivre?". Il ne semble pas dire que l'allégation elle-même est fausse; juste que votre intuition particulière ne fonctionne pas. Nous ne pouvons pas encore exclure que les aspects probabilistes du PPTM ne puissent pas tirer davantage profit de cet oracle. Le probabiliste TM a plus d'outils à sa disposition, mais l'outil pourrait ne pas fournir d'avantages stricts sans d'autres (comme l'oracle NP).

mdxn

Même avec l'hypothèse qu'un PRNG assez fort pour effondrer P et BPP existe, je ne vois pas pourquoi cela doit nécessairement impliquer BPP avec un oracle NP et P avec un oracle NP doit être le même. Normalement, les PRNG ont la garantie qu'aucun circuit polysize ne peut distinguer leur sortie de bits vraiment aléatoires. Mais pour les machines oracle, vous avez besoin de la garantie pour chaque circuit polysize avec des portes NP autorisées, et c'est plus fort. Impagliazzo-Wigderson relativise, mais vous devez renforcer l'hypothèse de dureté ( eccc.hpi-web.de/report/1998/055/comment/1/download )

Sasho Nikolov

Conséquences de

Réponses: