¿Prueba de contradicción para la desigualdad de P y NP?

Estoy tratando de argumentar que N no es NP igual usando teoremas de jerarquía. Este es mi argumento, pero cuando se lo mostré a nuestro maestro y después de la deducción, dijo que esto es problemático cuando no puedo encontrar una razón convincente para aceptar.

Comenzamos asumiendo que . Luego produce que a su vez sigue a . Tal como están las cosas, podemos reducir todos los idiomas en a . Por lo tanto, . Por el contrario, el teorema de la jerarquía de tiempo establece que debe haber un lenguaje , que no está en . Esto nos llevaría a concluir que está en , mientras que no está en , lo cual es una contradicción con nuestra primera suposición. Entonces, llegamos a la conclusión de que . $P=NP$ $\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$

¿Hay algo mal con mi prueba?

complexity-theory time-complexity p-vs-np índice_invertido
fuente

Por favor, escribe algo como en $\mathit{SAT}$ lugar de $SAT$ . Como Leslie Lamport escribió en su libro original de LaTeX, este último representa S veces A veces T.

Oliphaunt - reinstala a Mónica el

Mejor aún, use el complexitypaquete y simplemente escriba \SAT. (Supongo que eso no está disponible en esta pila, sin embargo.)

Oliphaunt - reinstalar a Monica el

@Oliphaunt ¿Por qué no sugerir una edición cuando puede mejorar la publicación? Aunque debo decir que aquí la diferencia (si la hay) es mucho más sutil de lo que esperaba.

Lagarto discreto

@Discretelizard A menudo lo hago, pero esta vez fue "demasiado trabajo" (estaba / estoy en el móvil). Introducir todos esos $ y \ es un trabajo complicado. Elegí educar en su lugar. (Esta decisión puede no haber sido completamente racional.)

Oliphaunt - reinstalar a Mónica el

Respuestas:

Luego produce ese que luego sigue ese . $SAT \in P$ $SAT \in TIME(n^k)$

Seguro.

Tal como están las cosas, podemos reducir todos los idiomas en a . Por lo tanto, . $NP$ $SAT$ $NP \subseteq TIME(n^k)$

No. Las reducciones de tiempo polinómico no son gratuitas. Podemos decir que lleva tiempo reducir el lenguaje a , donde es el exponente en la reducción de tiempo polinómica utilizada. Aquí es donde su argumento se desmorona. No hay finita tal que para todo tengamos . Al menos esto no se deduce de y sería una afirmación mucho más fuerte. $O(n^{r(L)})$ $L$ $SAT$ $r(L)$ $k$ $L \in NP$ $r(L) < k$ $P = NP$

Y esta afirmación más fuerte de hecho entra en conflicto con el teorema de la jerarquía de tiempo, que nos dice que no puede colapsar en , y mucho menos . $P$ $TIME(n^k)$ $NP$

orlp
fuente

No es solo el momento de la reducción en sí. Podría reducir a un problema mayor. Si puedo resolver X en O (n ^ 5), y puedo reducir un problema en Y en O (n ^ 6) a una instancia de X de tamaño O (n ^ 3), entonces necesito O (n ^ 15) en total.

gnasher729

Divertidamente, este argumento se aplica también a los problemas completos de PTIME, por ejemplo, HORNSAT, que se puede resolver en tiempo lineal (pero no todos los problemas en P son tiempo lineal).

cody

Supongamos que . Según la versión no determinista del teorema de la jerarquía de tiempo, para cualquier , hay un problema que no está en . Este es un resultado incondicional que no depende de ningún tipo de suposición, como $\mathrm{3SAT}\in\mathrm{NTIME}[n^k]$ $r$ $X_r\in\mathrm{NTIME}[n^r]$ $\mathrm{NTIME}[n^{r-1}]$ $\mathrm{P}\neq\mathrm{NP}$

Elija cualquier . Supongamos que tenemos una reducción determinista de a que se ejecuta en el tiempo . Produce una instancia de tamaño como máximo , que puede resolverse a tiempo como máximo . Al elegir , debemos tener , entonces . Esta función crece sin límite con . $r>k$ $X_r$ $\mathrm{3SAT}$ $n^t$ $\mathrm{3SAT}$ $n^t$ $(n^t)^k=n^{tk}$ $X_r$ $tk>r-1$ $t>(r+1)/k$ $r$

Esto significa que no hay límite en cuanto al tiempo que puede tomar reducir un problema arbitrario de a . Incluso si , todavía no hay límite sobre cuánto tiempo pueden llevar esas reducciones. Entonces, en particular, incluso si para algunas , no podemos concluir que , o incluso para algunas . $\mathrm{NP}$ $\mathrm{3SAT}$ $\mathrm{3SAT}\in \mathrm{P}$ $\mathrm{3SAT}\in\mathrm{DTIME}[n^{k'}]$ $k'$ $\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k'}]$ $\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k''}]$ $k''>k'$

David Richerby
fuente