¿P = NP en autómatas celulares de espacios hiperbólicos?
Leí hace unos años en este libro que los problemas de NP son tratables en el espacio de los autómatas celulares en el plano hiperbólico . ¿Qué significa esto? ¿ P = NPSegún estos libros/documentos?
Algunos extractos del documento:
Es bien sabido que si tenemos árboles binarios a nuestra disposición “gratis”, es posible resolver problemas NP en tiempo polinomial, ver [14, 5]. Sin embargo, no es inmediato implementar algoritmos de árboles binarios en el pentagrid, y el objetivo de esta sección es indicar cómo se puede proceder.
Según tengo entendido, el problema P = NP busca algoritmos de tiempo polinomial para resolver problemas complicados. De mi rápida mirada a través de los libros y papeles, parece sugerir que él ha resuelto el problema. ¿Qué me estoy perdiendo?
Aquí hay otro artículo, titulado En algunos espacios curvos, podemos resolver problemas NP-difíciles en tiempo polinomial: hacia el sueño de Matiyasevich .
Respuestas
El problema P vs NP es una pregunta sobre las máquinas de Turing$T$, porque las clases de complejidad P y NP se definen en términos de estas máquinas teóricas. Llamemos a estas clases$P_T$y$NP_T$de aquí en adelante. El artículo presenta una nueva máquina de computación teórica.$H$que tiene clases asociadas$P_H$(corre en tiempo polinomial en el autómata celular hiperbólico) y$NP_H$(se ejecuta en tiempo polinomial no determinista en el autómata celular hiperbólico).
El primer paso en este artículo es una prueba de que el problema 3SAT, un problema bien conocido$NP_T$-problema completo, se puede resolver en tiempo polinomial en esta máquina, es decir, este problema radica en$P_H$. A continuación, muestran que cualquier reducción de tiempo polinomial en una máquina de Turing se puede realizar en tiempo polinomial en su autómata hiperbólico. Dado que 3SAT es$NP_T$-completo, cualquiera$NP_T$instancia puede reducirse a una instancia 3SAT en tiempo polinomial (en$T$por definición, así también en$H$por su lema) y luego resolverse resolviendo 3SAT en politiempo, ambos en el autómata hiperbólico. En otras palabras, el resultado principal de este artículo (Teorema 1) se puede escribir como$NP_T \subseteq P_H$en nuestra notación. Esto no da una solución al problema P vs. NP, porque eso necesitaría relacionar las clases$NP_T$y$P_T$.
Tenga en cuenta que los autores incluyen algunos comentarios sobre el problema P vs. NP en la sección 4.2, donde afirman que su resultado es evidencia para P$\neq$NP (!):
Una tercera dirección consiste en la nueva luz arrojada sobre la cuestión P=NP en los escenarios ordinarios. Como el espacio hiperbólico tiene propiedades muy diferentes de las propiedades del espacio euclidiano, en particular, tiene muchas más direcciones, ¿no sería eso una pista favorable para demostrar que P$\neq$NP en condiciones euclidianas? Parece que desde hace diez años los trabajos en el campo de la complejidad inclinan a creer más en P$\neq$NOTARIO PÚBLICO. Aparentemente, el presente resultado también pertenece a esa tendencia.