Un problème de décision qui n'est pas connu pour être en PH mais qui sera en P si P = NP

28

Edit : Comme Ravi Boppana l'a correctement souligné dans sa réponse et Scott Aaronson a également ajouté un autre exemple dans sa réponse , la réponse à cette question s'est avérée «oui» d'une manière à laquelle je ne m'attendais pas du tout. J'ai d'abord pensé qu'ils n'avaient pas répondu à la question que je voulais poser, mais après réflexion, ces constructions répondent à au moins une des questions que je voulais poser, à savoir: «Existe-t-il un moyen de prouver un résultat conditionnel 'P = NP ⇒ L ∈P 'sans prouver le résultat inconditionnel L ∈PH? ”Merci, Ravi et Scott!


Existe-t-il un problème de décision L tel que les conditions suivantes soient toutes les deux remplies?

  • L n'est pas connu pour être dans la hiérarchie polynomiale.
  • On sait que P = NP impliquera L ∈P.

Un exemple artificiel est aussi bon qu'un exemple naturel. De plus, bien que j'utilise la lettre « L », cela peut être un problème de promesse au lieu d'une langue si cela aide.

Contexte . Si nous savons qu'un problème de décision L est dans la hiérarchie polynomiale, alors nous savons que «P = NP ⇒ L ∈P». L'intention de la question est de demander si l'inverse est vrai. Si un langage L satisfaisant aux deux conditions ci-dessus existe, il peut être considéré comme une preuve de l'échec de l'inverse.

La question a été motivée par le commentaire intéressant de Joe Fitzsimons à ma réponse à la question de Walter Bishop « Conséquences de #P = FP ».

Tsuyoshi Ito
la source
Prouver un négatif universel est toujours difficile (euh), mais je serais surpris si un tel langage existait. La conjecture généralisée Linial-Nisan (si elle s'était avérée vraie) n'aurait pas impliqué ce que vous demandez, je ne crois pas. Cela aurait simplement signifié que BQP n'était pas contenu dans PH. Si PH s'est effondré en P, BQP n'aurait toujours pas été contenu dans P (H).
Daniel Apon
Demandez-vous s'il existe une classe de complexité X st X n'est pas un sous-ensemble de PH, et P = NP -> X = P?
Philip White
@Philip: Oui, mais je ne pense pas que cela change le problème car on peut généralement convertir un problème de décision L en une classe X de problèmes de décision réductibles en L. Au moins c'était mon intention de poser cette question en termes de problèmes de décision .
Tsuyoshi Ito
Peut-être voulez-vous exiger que la langue soit en quelque sorte proche de PH, en plus de vos exigences actuelles? Peut-être, par exemple, dans PSPACE (bien que l'on puisse dire à quel point PSPACE est proche de PH; voir S. Fenner, S. Homer, M. Schaefer, R. Pruim. Hiérarchies hyperpolynomiales et saut polynomial. Théorie informatique. Volume 262 ( 2001), p. 241-256 cse.sc.edu/~fenner/papers/hyp.pdf ). Ou peut-être voulez-vous vraiment demander une telle langue naturelle .L
Joshua Grochow
@Joshua: Merci pour le commentaire et la référence. Comme indiqué dans la mise à jour (révision 3), maintenant je pense que j'avais posé la bonne question (contrairement à ce que j'ai ajouté dans la révision 2). J'avais voulu savoir "Existe-t-il un moyen de prouver un résultat conditionnel 'P = NP ⇒ L∈P' sans prouver le résultat inconditionnel L∈PH?" Pour cela, le caractère naturel du problème ne devrait pas être exigé car une fois là est une méthode de preuve, elle devrait s'appliquer également aux exemples naturels et artificiels.
Tsuyoshi Ito du

Réponses:

26

Puisque cela ne vous dérange pas un langage artificiel, que diriez-vous de définir comme étant vide si P est égal à NP et comme étant le problème d'arrêt si P n'est pas égal à NP. D'accord, c'est un peu une triche, mais je pense que vous devrez reformuler le problème pour éviter de telles tricheries. L

Ravi Boppana
la source
5
Merci, je vois le point (définir L = {M: la machine de Turing M s'arrête et P ≠ NP}). Bien sûr, cela ne répond pas à ce que je voulais poser, mais je suppose que je dois réfléchir davantage pour formuler la question que je voulais poser correctement.
Tsuyoshi Ito du
30

Si un exemple artificiel est vraiment aussi bon qu'un naturel, alors je peux en effet fournir un tel exemple!

Edit: En outre, mon exemple est "un peu" moins une triche que celui suggéré par Ravi Boppana (où nous prenons L pour être la langue vide si P = NP et le problème d'arrêt autrement), en ce que je définirai la langue L en donnant une procédure finie pour décider si L pour toute entrée x. A aucun moment, décider si x∈L nécessite de résoudre une question mathématique "non bornée" telle que P vs. NP.x


Sans plus tarder: laisser M1,M2,...être une énumération des machines Turing polytime. Pour tout , soit M t ( n ) le premier lexicographiquement M i qui décide correctement 3SAT sur toutes les entrées de longueur n ou moins. Définissez ensuite le langage L comme suit: pour toutes les entrées x de taille n , x L si et seulement si la machine de Turing codée par x s'arrête au plus n t ( n )nMt(n)Minxnxxnt(n) étapes lors de l'exécution sur une bande vierge.

Allégation 1: si P = NP, alors L P.

Preuve: si P = NP, alors il y a un certain fixe qui résout 3SAT pour toutes les entrées; d'où t ( n ) Mi pour tout n . QEDt(n)in

Allégation 2: Si P NP, alors L P.

Preuve: si augmente sans limite, alors nous pouvons simplement appliquer le théorème de la hiérarchie temporelle. QEDt(n)

Maintenant, non seulement L n'est pas dans P en supposant P NP: on suppose qu'il ne serait pas non plus en PH (ou même PSPACE)!

Par ailleurs, je me demande si quelqu'un peut améliorer la construction ci-dessus, pour obtenir un langage L qui est en P si P = NP, mais prouvablement pas en PH ou PSPACE si P NP?

Scott Aaronson
la source
1
Merci! Je n'ai pas pu modifier la construction pour rendre prouvable la non-adhésion à PH, mais cela suffit pour me convaincre que l'ajout de la condition que L est décidable avec une preuve constructive de la décidabilité ne changera probablement pas beaucoup la situation. Hmm.
Tsuyoshi Ito du
3
J'accepterai la réponse de Ravi Boppana parce que la sienne a été la première à arriver, bien que je veuille accepter les deux parce que les deux m'ont permis de mieux comprendre le problème. J'espère que tu comprends….
Tsuyoshi Ito du
4
Agréable. C'est une excellente réponse.
Daniel Apon
@Tyson Williams: Juste au cas où vous ne l'auriez pas réalisé, veuillez faire très attention à ne pas introduire d'erreur lorsque vous éditez un post par d'autres utilisateurs. Heureusement que Joe l'a remarqué et l'a corrigé.
Tsuyoshi Ito
18

Répondant à la question de Scott Aaronson, mais un peu trop long pour un commentaire, voici une construction d'un langage tel que P = NL implique L P , mais P N P implique L P HP=NPLPPNPLPH .

Soit et t ( n ) comme dans la construction de Scott. On fait en sorte que L ne se réduise pas à Σ k S A T pour chaque k , mais on ne le fait que si t ( n ) (ie si P N P ). La construction se déroule par étapes. Au stade s = ( i , j )M1,M2,M3,t(n)LΣkSATkt(n)PNPs=(i,j) (en utilisant une bijection facilement calculable et facilement inversible ), nous nous assurons que M i n'est pas une réduction de plusieurs de L à Σ j S A T . Soit nΣΣ×ΣMiLΣjSAT le plus petit entier tel quet( n s )>t( n s - 1 )(cas de base: n 0 =1). S'il existe un tel entier n snst(ns)>t(ns1)n0=1ns , alors définissez . S'il n'y a pas un tel entier n s , nous laissons L vide pour toujours.L(1ns)=1ΣkSAT(Mi(1ns))nsL

Si , alors t ( n ) comme n , donc il y a toujours un tel n s , d' où L est pas dans P H . Si P = N P , alors mon L est différent de ne finiment Scott de L , et est donc dans P .PNPt(n)nnsLPHP=NPLLP

Joshua Grochow
la source
Merci pour votre réponse, mais je ne sais pas si je comprends la construction. Il me semble que pour calculer , il pourrait être nécessaire de chercher indéfiniment, et donc il me semble que nous n'avons pas d'algorithme explicite pour décider du langage L. Si nous n'avons pas besoin d'un algorithme explicite, Ravi Boppana répond montre qu'il existe un langage L tel que P = NP⇒L∈P et P ≠ NP⇒L∉R (ie, L est indécidable). ns
Tsuyoshi Ito
1
@Tsuyoshi Ito: Je ne pense pas que vous ayez à calculer donnés s pour décider de L; tout ce que vous avez à faire est, sur l'entrée 1 n , de décider si n est de la forme n s pour certains s et de déterminer de quel s il s'agit (le cas échéant). Voici comment: sur l'entrée 1 n , calculez t ( n ) et calculez t ( m ) pour tout m < n . S'il y a un m < n tel que t ( nnss1nnnsss1nt(n)t(m)m<nm<n , alors n n'est pas n s pour tout st(n)=t(m)nnss , donc . Sinon, déterminez quelle étape s correspond à ce n s (ce qui peut être fait puisque vous avez calculé toutes les valeurs précédentes de t ), puis calculez L ( 1 n ) comme décrit dans la réponse. L(1n)=0snstL(1n)
Joshua Grochow