La solución al problema NP=P debe ser obtenida en el paradigma de la computación con máquinas de Turing.
Sin embargo, hay otros paradigmas de computación que no son Turing, como la memcomputación (un tipo de computación analógica neuronal basada en memristores y otros memdispositivos).
Un nuevo artículo presenta un memcomputador que implementa un algoritmo NP completo y demuestra que está en P. Por tanto, todo memalgoritmo NP-c es P y en la memcomputación NP=P.
Por supuesto, esto no sorprenderá a los expertos. Existe una demostración matemática de que un memcomputador universal es equivalente a una máquina de Turing no determinista universal. Lo que quiero destacar aquí es que los memcomputadores no son una entelequia teórica, se pueden implementar de forma física y el nuevo artículo presenta una implementación física concreta del algoritmo NP-c estudiado.
El nuevo artículo técnico es Fabio L. Traversa, Chiara Ramella, Fabrizio Bonani, Massimiliano Di Ventra, “Memcomputing NP-complete problems in polynomial time using polynomial resources,” arXiv:1411.4798 [cs.ET]. La memcomputación nació con Massimiliano Di Ventra, Yuriy V. Pershin, “The parallel approach,” Nature Physics 9: 200-202, 2013.
La demostración de la equivalencia entre memcomputación y computación Turing no determinista se encuentra en F. L. Traversa, M. Di Ventra, “Universal Memcomputing Machines,” IEEE Transaction on Neural Networks and Learning Systems, Accepted, 2014; arXiv:1405.0931 [cs.NE].
Un memcomputador está inspirado en el encéfalo: una máquina intrínsecamente paralela, que presenta polimorfismo funcional y que tiene capacidad de almacenar más información que el número de elementos de memoria que contiene de forma explícita (cada elemento de memoria es un dispositivo capaz de almacenar un dato continuo, en esencia un número real).
El memcomputador está formado por cierto número de memprocesadores. Usando sistemas físicos continuos se puede implementar un memprocesador (obviamente los números reales no existen en la realidad física, pero se aproximan bastante bien).
El nuevo artículo presenta una implementación concreta de un memprocesador basada en tecnologías microelectrónicas estándares.
Por ahora se trata de un prototipo de laboratorio de pequeño tamaño, pero en teoría debería ser escalable (basta incrementar linealmente el número de memprocesadores).
El nuevo artículo ha implementado una versión del problema NP completo llamado Problema del Subconjunto Suma (SSP por Subset-Sum Problem).
El nuevo memcomputador resuelve este problema en tiempo polinómico con un número polinómico de memprocesadores. Obviamente, demostrar que para un memcomputador NP=P no resuelve el problema del Milenio NP=P, cuya solución debe estar en el paradigma de las máquinas de Turing.
Como se ha demostrado que la memcomputación es equivalente a las máquinas de Turing no deterministas, es obvio que NP=P en el paradigma de la memcomputación.
El nuevo artículo ha implementado microelectrónicamente un memcomputador con seis memprocesadores y ha resuelto el problema SSP usando 4, 5 y 6 memprocesadores.
No quiero entrar en los detalles técnicos, que sólo tienen interés para los expertos (y que están muy bien descritos en los artículos que cito más arriba).
El diseño microelectrónico de cada memprocesador es fácil de copiar por cualquier ingeniero electrónico.
Por ello espero que en los próximos meses haya un gran número de memcomputadores en los laboratorios de microelectrónica de las universidades y de los institutos de investigación por todo el mundo. Además, en teoría, el diseño usado para conectar los memprocesadores es escalable. Aún así, no debemos olvidar que se trata de un prototipo.
Serán necesarios importantes avances tecnológicos para lograr atacar problemas NP completos de interés práctico (que requieren miles de memprocesadores).
Aún así, en mi opinión, se trata de un trabajo muy prometedor.
http://francis.naukas.com/
