Classes de complexité potentiellement égales sans relativisations contradictoires connues

Quels sont quelques exemples de paires de classes de complexité et telles que $A$ $B$

on ne sait pas si , et $A=B$
nous ne connaissons pas non plus de relativisations contradictoires (c'est-à-dire que nous ne connaissons pas les oracles et tels que et )? $P$ $Q$ $A^P = B^P$ $A^Q \ne B^Q$

Pour formuler la question d'une autre manière, quelles sont les exceptions à l'heuristique selon lesquelles si l'on ne parvient pas à comprendre des relativisations contradictoires, il est alors facile de résoudre la question d'égalité de manière catégorique?

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

Est-ce que deux classes A et B pour lesquelles nous ne savons pas prouver une séparation oracle entre A et B suffiraient pour répondre à votre question? (En supposant qu'il est possible que A et B soient égaux.)

Robin Kothari

Accepteriez-vous des exemples d'implications entre égalités, plutôt que des égalités uniques? Par exemple, nous ne savons pas si NP = UP implique que le PH s'effondre, mais nous n'avons pas non plus d'oracle dans lequel cette implication est fausse.

Joshua Grochow

@JoshuaGrochow: C'est intéressant, même si je suis un peu plus intéressé par le type spécifique d'exemple que j'ai décrit.

Timothy Chow du

@Robin Kothari: Si nous ne connaissons pas un oracle Q, a fortiori nous ne connaissons pas les oracles P et Q, donc la seule façon que je vois pour (A, B) de satisfaire vos besoins mais pas le mien est si nous savons que A = B mais nous ne connaissons pas d'oracle qui les sépare. Je suppose qu'il pourrait être intéressant de voir un exemple de A et B tel que A = B mais il est plausible (mais pas connu) qu'ils puissent être séparés par un oracle, mais ce n'est pas vraiment ce que je demandais.

Timothy Chow du

Réponses:

Je pense que le plus grand exemple de ce type à l'heure actuelle est (temps polybomial quantique) vs (la hiérarchie polynomiale du temps). Des efforts importants ont été déployés pour les séparer par rapport à un oracle, sans succès. (Bien sûr , un oracle assez puissant fera les égalent.) Et le meilleur résultat de confinement est connu que est . $BQP$ $PH$ $BQP$ $PP$

Quelques références pour les attaques contre le problème Oracle: http://arxiv.org/abs/0910.4698 http://arxiv.org/abs/1007.0305

Ryan Williams
la source

En fait , le meilleur résultat connu est

, où

est (entre autres) la plus grande sublcass d'intervalle définissable de

tel que

. Je ne connais aucun intérêt pour la classe

dehors de sa relation avec

et avec

B Q P \subseteq A W P P \subseteq P P

$\mathsf{BQP \subseteq AWPP \subseteq PP}$

A W P P

$\mathsf{AWPP}$

P P

$\mathsf{PP}$

P P^{A W P P} = P P

$\mathsf{PP^{AWPP} = PP}$

A W P P

$\mathsf{AWPP}$

B Q P

$\mathsf{BQP}$

P P

$\mathsf{PP}$ , donc comme un raffinement, c'est un peu un point technique, mais c'est parti.

Niel de Beaudrap du

Dans ce sens, on ne sait pas non plus comment séparer BQP de AM, ni même QMA de AM.

Robin Kothari

Existe-t-il un oracle connu pour séparer de ? $\mathsf{P}^{\#\mathsf{P}}$ $\mathsf{PSPACE}$

Ryan O'Donnell
la source

Je suis à peu près sûr que la question était plus rhétorique, c'est-à-dire "je pense que c'est une réponse, mais peut-être y a-t-il un oracle connu dont je ne suis pas au courant"

Joshua Grochow

Oui, merci Josh. En connaissez-vous un? C'est très difficile à rechercher, mais je me souviens ne pas avoir pu connaître son existence la dernière fois que j'ai essayé.

Ryan O'Donnell