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].
No hay comentarios:
Publicar un comentario