Algorítmica y complejidad computacional. ¿?.

Es un artículo recién salido del horno, de este año, 2016. Se trata de una (otra) supuesta demostración más del famoso problema de esta disciplina. No es la primera publicación del autor (cuyo nombre por lo visto no es más que  un pseudonimo) en este sentido y seguramente será incorrecta.

Nos ha llamado la atención pues combina muchos de los temas que nos han interesado en relación al tema de la complejidad computacional (por su relación con los resultados de la patente: versión sucinta de problemas computacionales, problema de recorridos hamiltonianos, clases EXP y NEXP etc…) y sobre los que hemos publicado en este blog.

La demostración parte del resultado conocido “si P=NP entonces EXP=NEXP” y deriva una contradicción.

Extracto (en el que muestra la estrategia a ojo de pájaro de la demostración).

EXP and NEXP are nothing else but P and NP on exponentially more succinct input [4]. It is known the succinct version of the problem HAMILTON PATH, that is called SUCCINCT HAMILTON PATH, is in NEXP–complete [4]. We shall prove if we assume that P = NP, then the language SUCCINCT HAMILTON PATH would be in P too. However, this would imply P = EXP [4]. But, this is a false result [4]. In this way, we shall claim that P , NP as a consequence of applying the Reductio ad absurdum rule.

Recordamos por otra parte que el estatus de (una versión) de la inversa de la proposición de la que parte este autor, es decir “si SUBEXP=EXP=NEXP, entonces P=NP” no está claro. ¿ Está abierta o se sabe que no es cierta ? Realmente ahora mismo no recuerdo bien, aunque si tengo claro que si metemos la clase SUBEXP en la identidad entonces entran en juego las hipótesis SETH y ETH. Esta es la vía sobre la que nosotros nos estuvimos documentando en su momento.

En fin, no se si merece la pena hacer una lectura del artículo en profundidad, sobre todo teniendo en cuenta lo que nos cuesta ahora mismo leer sobre estos temas y el poco tiempo sobre el que disponemos…

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: