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

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 que$\mathit{SAT} \in P$$\mathit{SAT} \in TIME(n^k)$$NP$$\mathit{SAT}$$NP \subseteq TIME(n^k)$$A \in TIME(n^{k+1})$$TIME(n^k)$$A$$P$$NP$$P \neq NP$ .

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

Il en résulte alors que $SAT \in P$ qui lui-même suit alors que $SAT \in TIME(n^k)$ .

Sûr.

Comme stands, nous sommes en mesure de faire réduire toutes les langues $NP$ à $SAT$ . Par conséquent, $NP \subseteq TIME(n^k)$ .

Non. Les réductions de temps polynomiales ne sont pas gratuites. On peut dire qu'il faut $O(n^{r(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 $L \in NP$ 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(n^k)$ , et encore moins tous $NP$ .

Supposons que $\mathrm{3SAT}\in\mathrm{NTIME}[n^k]$ . Par la version non déterministe du théorème de la hiérarchie temporelle, pour tout  $r$ , il existe un problème $X_r\in\mathrm{NTIME}[n^r]$ qui n'est pas dans $\mathrm{NTIME}[n^{r-1}]$ . Il s'agit d'un résultat inconditionnel qui ne dépend d'aucune sorte d'hypothèse telle que $\mathrm{P}\neq\mathrm{NP}$

Choisissez n'importe quel $r>k$ . Supposons que nous ayons une réduction déterministe de $X_r$ à $\mathrm{3SAT}$ qui s'exécute dans le temps  $n^t$ . Il produit une instance $\mathrm{3SAT}$ de taille au plus  $n^t$ , qui peut être résolue dans le temps au plus $(n^t)^k=n^{tk}$ . Par notre choix de  $X_r$ , nous devons avoir $tk>r-1$ , 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 $\mathrm{NP}$ problème $\mathrm{3SAT}$ . Même si $\mathrm{3SAT}\in \mathrm{P}$ , il n'y a toujours pas de limite sur la durée de ces réductions. Ainsi, en particulier, même si $\mathrm{3SAT}\in\mathrm{DTIME}[n^{k'}]$ pour certains  $k'$ , nous ne pouvons pas conclure que $\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k'}]$, ou même$\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k''}]$pour certains$k''>k'$.