Prova de contradição para a desigualdade de P e NP?

Estou tentando argumentar que N não é igual a NP usando teoremas de hierarquia. Esse é o meu argumento, mas quando mostrei ao nosso professor e, após dedução, ele disse que isso é problemático, onde não consigo encontrar uma razão convincente para aceitar.

Começamos assumindo que $P=NP$ . Então, produz $\mathit{SAT} \in P$ que por sua vez segue a $\mathit{SAT} \in TIME(n^k)$ . Como stands, somos capazes de fazer reduzir todas as línguas $NP$ a $\mathit{SAT}$ . Portanto, $NP \subseteq TIME(n^k)$ . Pelo contrário, o teorema da hierarquia do tempo afirma que deveria haver uma linguagem$A \in TIME(n^{k+1})$ , isso não está em$TIME(n^k)$ . Isso nos levaria a concluir que$A$ está em$P$ , enquanto não estiver em$NP$ , que é uma contradição para a nossa primeira suposição. Assim, chegamos à conclusão de que$P \neq NP$ .

Existe algo errado com a minha prova?

Então, produz $SAT \in P$ que por sua vez segue a $SAT \in TIME(n^k)$ .

Certo.

Como stands, somos capazes de fazer reduzir todas as línguas $NP$ a $SAT$ . Portanto, $NP \subseteq TIME(n^k)$ .

Não. As reduções de tempo polinomiais não são gratuitas. Podemos dizer que leva $O(n^{r(L)})$ tempo para reduzir a linguagem $L$ para $SAT$ , onde $r(L)$ é o expoente na redução de tempo polinomial usada. É aqui que seu argumento se desfaz. Não existe um $k$ finito que, para todo $L \in NP$ , tenhamos $r(L) < k$ . Pelo menos isso não segue de $P = NP$ e seria uma afirmação muito mais forte.

E esta afirmação mais forte faz de fato conflito com o teorema de hierarquia de tempo, que nos diz que $P$ não pode entrar em colapso em $TIME(n^k)$ , muito menos todos $NP$ .

Suponha que $\mathrm{3SAT}\in\mathrm{NTIME}[n^k]$ . Pela versão não determinística do teorema da hierarquia de tempo, para qualquer  $r$ , existe um problema $X_r\in\mathrm{NTIME}[n^r]$ que não está em $\mathrm{NTIME}[n^{r-1}]$ . Este é um resultado incondicional que não depende de nenhum tipo de suposição, como $\mathrm{P}\neq\mathrm{NP}$

Escolha qualquer $r>k$ . Suponha que tenhamos uma redução determinística de $X_r$ para $\mathrm{3SAT}$ que é executada no tempo  $n^t$ . Ele produz uma instância de $\mathrm{3SAT}$ de tamanho no máximo  $n^t$ , que pode ser resolvida no tempo no máximo $(n^t)^k=n^{tk}$ . Pela nossa escolha de  $X_r$ , devemos ter $tk>r-1$ , então $t>(r+1)/k$ . Esta função cresce sem delimitar com $r$ .

Isto significa que não há nenhum limite de quanto tempo ele pode levar a uma redução arbitrária $\mathrm{NP}$ problema para $\mathrm{3SAT}$ . Mesmo se $\mathrm{3SAT}\in \mathrm{P}$ , ainda não há limite de quanto tempo essas reduções podem levar. Assim, em particular, mesmo que $\mathrm{3SAT}\in\mathrm{DTIME}[n^{k'}]$ por alguns  $k'$ , não podemos concluir que $\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k'}]$, ou mesmo$\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k''}]$$k''>k'$