Preuve de contradiction pour l'inégalité de P et NP?

10

J'essaie de faire valoir que N n'est pas égal à NP en utilisant des théorèmes de hiérarchie. C'est mon argument, mais quand je l'ai montré à notre professeur et après déduction, il a dit que c'était problématique où je ne trouvais pas de raison impérieuse d'accepter.

Nous commençons en supposant que P=NP . Ensuite, il donne que qui lui-même suit alors que . En l'état, nous pouvons réduire chaque langue de à . Par conséquent, NP \ subseteq TIME (n ^ k) . Au contraire, le théorème de la hiérarchie temporelle stipule qu'il devrait y avoir un langage A \ dans TIME (n ^ {k + 1}) , qui n'est pas dans TIME (n ^ k) . Cela nous amènerait à conclure que A est dans P , mais pas dans NP , ce qui est en contradiction avec notre première hypothèse. Nous sommes donc arrivés à la conclusion queSATPSATTIME(nk)NPSATNPTIME(nk)ATIME(nk+1)TIME(nk)APNPPNP .

Y a-t-il un problème avec ma preuve?

index_inverti
la source
2
Veuillez écrire quelque chose comme $\mathit{SAT}$au lieu de $SAT$. Comme Leslie Lamport l'a écrit dans son livre LaTeX original, ce dernier signifie S fois A fois T.
Oliphaunt - réintègre Monica le
Mieux encore, utilisez le complexitypackage et écrivez simplement \SAT. (Je suppose que ce n'est pas disponible sur cette pile, cependant.)
Oliphaunt - réintègre Monica le
@Oliphaunt Pourquoi ne pas suggérer une modification lorsque vous pouvez améliorer la publication? Bien que je doive dire qu'ici la différence (s'il y en a) est beaucoup plus subtile que je ne m'y attendais.
Lézard discret
1
@Discretelizard Je le fais souvent, mais c'était "trop ​​de travail" cette fois (j'étais / suis sur mobile). Entrer tous ces $ et \ est un travail difficile. J'ai plutôt choisi d'éduquer. (Cette décision n'était peut-être pas entièrement rationnelle.)
Oliphaunt - réintègre Monica le

Réponses:

55

Il en résulte alors que SATP qui lui-même suit alors que SATTIME(nk) .

Sûr.

Comme stands, nous sommes en mesure de faire réduire toutes les langues NP à SAT . Par conséquent, NPTIME(nk) .

Non. Les réductions de temps polynomiales ne sont pas gratuites. On peut dire qu'il faut O(nr(L)) pour réduire le langage L à SAT , où r(L) est l'exposant de la réduction de temps polynomiale utilisée. C'est là que votre argument s'effondre. Il n'y a pas de k fini tel que pour tout LNP on ait r(L)<k . Au moins, cela ne découle pas de P=NP et serait une déclaration beaucoup plus forte.

Et cette affirmation plus forte ne fait en conflit avec le théorème de hiérarchie de temps, ce qui nous dit que P ne peut pas s'effondrer dans TIME(nk) , et encore moins tous NP .

orlp
la source
1
Ce n'est pas seulement le moment de la réduction elle-même. Vous pourriez réduire à un problème plus important. Si je peux résoudre X en O (n ^ 5) et que je peux réduire un problème en Y en O (n ^ 6) à une instance de X (n ^ 3) de taille O, alors j'ai besoin de O (n ^ 15) au total.
gnasher729
De manière amusante, cet argument s'applique également aux problèmes complets de PTIME, par exemple HORNSAT, qui peut être résolu en temps linéaire (mais tous les problèmes de P ne sont pas linéaires).
cody
8

Supposons que 3SATNTIME[nk] . Par la version non déterministe du théorème de la hiérarchie temporelle, pour tout  r , il existe un problème XrNTIME[nr] qui n'est pas dans NTIME[nr1] . Il s'agit d'un résultat inconditionnel qui ne dépend d'aucune sorte d'hypothèse telle que PNP

Choisissez n'importe quel r>k . Supposons que nous ayons une réduction déterministe de Xr à 3SAT qui s'exécute dans le temps  nt . Il produit une instance 3SAT de taille au plus  nt , qui peut être résolue dans le temps au plus (nt)k=ntk . Par notre choix de  Xr , nous devons avoir tk>r1 , donc t>(r+1)/k . Cette fonction croît sans limite avec r .

Cela signifie qu'il n'y a pas de limite sur combien de temps cela peut prendre pour réduire l'arbitraire NP problème 3SAT . Même si 3SATP , il n'y a toujours pas de limite sur la durée de ces réductions. Ainsi, en particulier, même si 3SATDTIME[nk] pour certains  k , nous ne pouvons pas conclure que NPDTIME[nk], ou mêmeNPDTIME[nk]pour certainsk>k.

David Richerby
la source