Y a-t-il un problème informatique qui est en temps quasi polynomial mais qui n'est (peut-être) pas en

Le temps quasi-polynomial, ou QP pour faire court, est une classe de complexité sur la machine de Turing déterministe. Voici la définition précise: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp

Alors que βP est une classe de complexité de non-déterminisme limité. Voici la définition précise: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap

Il est facile de voir que n'importe quelle machine de βP peut être simulée par une machine de QP, à savoir, βP $\subseteq$ QP.

Mais avons-nous un exemple, un problème qui est en QP mais pas en βP, même si nous n'avons juste aucune preuve précise que le problème n'est pas en βP?

cc.complexity-theory complexity-classes Arthur Kexu-Wang
la source

Soit f la fonction number_of_states_, et considérons le problème

$\hspace{2.36 in}$ "Est-ce que M s'arrête tout au plus (f (M))

étapes « ?.

^{\log (f (M))}

$^{\hspace{.02 in}\log(\hspace{.04 in}f(M))}$

Réponses:

Bien que je ne sais pas spécifique (conjecturé) par exemple dans , il y a encore des preuves assez convaincantes que est un bon sous - ensemble de . À savoir, ces classes se comportent très différemment dans leur relation avec : $QP-\beta P$ $\beta P$ $QP$ $NP$

Il ressort de la définition que . $\bullet$ $\beta P\subseteq NP$

D'autre part, ne sait pas, et il serait très difficile à prouver, car il implique . (En fait, c'est une affirmation encore plus forte que ) $\bullet$ $QP\subseteq NP$ $P\neq NP$ $P\neq NP$

Un tel comportement très différent par rapport à semble fournir une raison assez forte de croire que . $NP$ $\beta P\neq QP$

Andras Farago
la source

De plus, il semble peu probable que

soit fermé sous complément.

β P

$\beta P$

Emil Jeřábek

Puisque, comme vous l' avez mentionné

signifie

. À titre de suivi, quel serait le résultat de

dans la hiérarchie de la complexité et cela aurait-il un impact sur le problème

Q P \subseteq N P

$QP\subseteq NP$

P \neq N P

$P\neq NP$

N P \subseteq Q P

$NP \subseteq QP$

N P \subset Q P

$NP \subset QP$

P v s N P

$P vs NP$

TheoryQuest1

Oui. Nous avons un tel problème. C'est un problème d'isomorphisme graphique. Babai a prouvé que GI est en QP . Ma compréhension est que la preuve de Babai ne donne pas de limite supérieure de non-déterminisme limitée ( ) sur la complexité du GI. $\beta P$

Nous avons aucune preuve que GI est en $\beta P$ . De plus, nous n'avons pas de preuve que l'IG ne peut pas être résolu en utilisant le non-déterminisme poly-logarithmique.

Voir cet article connexe .

Ce post de CS Theory par @Salamon indique que nous ne savons même pas si le GI peut être décidé avec un non-déterminisme borné à racine carrée et encore moins un non-déterminisme poly-logarithmique.

Mohammad Al-Turkistany
la source

Cependant, je pense que beaucoup de gens conjecturent que GI est en P.

Thomas

@Thomas Babai dans son article a indiqué qu'il était contre cette conjecture.

Mohammad Al-Turkistany

Êtes-vous si sûr que l'algorithme de Babai n'est pas en

β P

$\beta P$

Joshua Grochow

@ MohammadAl-Turkistany Ironiquement, la question sur MO que vous citez (à la fois dans votre réponse et dans votre commentaire) est posée par le PO lui-même il y a 10 mois et n'a pas de réponse (à ce jour). Je ne sais pas dans quelle mesure cela donne du crédit à votre argument - cela implique seulement que "nous n'avons aucune preuve que GI est en

référencé sur MathOverflow " au mieux.

β P

$\beta P$

Clement C.

@JoshuaGrochow Oui, le commentaire est plus spécifique (soulignant la partie spécifique du diplôme). Mais la réponse fait simplement référence à la question sur MO comme ce que je considère comme un indice fort de l'affirmation qu'il n'y a aucune preuve - ce qui me semble circulaire.

Clement C.