¿P = NP en Autómatas Celulares Hiperbólicos de los Espacios?

Question

Leí hace un par de años en este libro que NP problemas son manejables en el espacio de los autómatas celulares en el plano hiperbólico.¿Qué significa esto?¿ P = NP de acuerdo a estos libros o papeles?

Algunos extractos de la ponencia:

Es bien sabido que si tenemos árboles binarios a nuestra disposición "gratis", es posible resolver problemas del tipo NP-problemas en el polinomio tiempo, ver [14, 5].Sin embargo, no es inmediata para implementar árbol binario de algoritmos en la pentagrid, y el objetivo de esta sección es indicar cómo se puede proceder.

Desde mi entender, el P = NP el problema está buscando polinomio de tiempo de algoritmos para resolver problemas complicados.Desde mi mirada superficial a través de los libros y papeles, parece sugerir que él ha resuelto el problema.Lo que me estoy perdiendo?

Aquí es otro documento, titulado En Algunos Espacios Curvos, Podemos Resolver problemas del tipo NP-Duro de Problemas en el Polinomio de Tiempo:Hacia Matiyasevich del Sueño.

Answer 1

El P vsNP problema es una pregunta acerca de las máquinas de Turing $T$, debido a la complejidad de las clases P y NP son definidos en términos de estos teóricos de las máquinas.Vamos a llamar a estas clases $P_T$ y $NP_T$ a partir de ahora.El documento presenta un nuevo teóricos de cálculo de la máquina $H$ tiene asociados a las clases $P_H$ (se ejecuta en el polinomio de tiempo en el hiperbólico autómata celular) y $NP_H$ (se ejecuta en un no-determinista polinomio tiempo en el hiperbólico autómata celular).

El primer paso en este trabajo es una prueba de que el 3SAT problema, un conocido $NP_T$-completar problema, puede ser resuelto en el polinomio tiempo en esta máquina, es decir,este problema radica en $P_H$.A continuación, se muestran cualquier polinomio reducción de tiempo en una máquina de Turing puede ser realizado en el polinomio de tiempo en sus hiperbólico autómata.Desde 3SAT es $NP_T$-completar, cualquier $NP_T$ instancia puede ser reducido a un 3SAT ejemplo, en el polinomio de tiempo (en $T$ por definición, así también en la $H$ por su lema) y, a continuación, ser resuelto mediante la resolución de 3SAT en el poli-tiempo, tanto en el hiperbólico autómata.En otras palabras, el resultado principal de este documento (Teorema 1) puede ser escrita como $NP_T \subseteq P_H$ en nuestra notación.Esto no quiere dar una solución a la P vsNP problema, debido a que se tendría que relacionar las clases $NP_T$ y $P_T$.

Tenga en cuenta que los autores incluyen algunas observaciones sobre los P vsNP problema en la sección 4.2, en la que afirman que su resultado es la evidencia para P$ eq$NP (!):

Una tercera dirección se compone de la nueva luz derramada en la P=NP pregunta en el valores normales.Como el espacio hiperbólico tiene propiedades que son muy diferentes de las propiedades del espacio euclidiano, en particular, tiene muchas más direcciones, no tendría que ser un indicio favorable para probar que P$ eq$NP en euclidiana condiciones?Parece que durante los últimos diez años las obras en el campo de la complejidad de la inclinación de las personas a creer más en P$ eq$NP.Al parecer, el actual resultado también pertenece a esa tendencia.