En la memcomputación se cumple NP=P

Por Francisco R. Villatoro, el 21 noviembre, 2014. Categoría(s): Ciencia • Física • Informática • Noticias • Physics • Science ✎ 9

Dibujo20141121 memcomputing architecture and connection scheme - arxiv

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].

Dibujo20141121 solution tree np-complete problem implemented in universal memcomputing machine - arxiv

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).

Dibujo20141121 Scheme of the memcomputing architecture used in this work to solve the subset-sum problem - arxiv

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.

Dibujo20141121 spectra internal collective state three different networks 4 5 6 memprocessor - arxiv

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).

Dibujo20141121 memprocessor implementation - arxiv

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.

El lector inquieto se preguntará, si la memcomputación está inspirada en el encéfalo humano, ¿funciona nuestra mente gracias a la memcomputación? ¿Puede nuestra mente resolver problemas NP en tiempo polinómico y con un número polinómico de neuronas? No lo sabemos. Pero el campo de la memcomputación me parece realmente fascinante.

 



9 Comentarios

  1. ¿Es esto una aproximación física de http://en.wikipedia.org/wiki/Real_computation ?
    La última frase de la wiki es «Unlimited precision real numbers in the physical universe are prohibited by the holographic principle and the Bekenstein bound». Así que si entiendo bien, no ofrece nada que no se pueda hacer con un computador clásico, ya que su precisión tiene que estar limitada y podemos hacer que un computador clásico trabaje con esa misma precisión.

    1. Cristóbal, no, es computación analógica, pero no es computación real.

      Por otro lado, parece que confundes computabilidad (o calculabilidad) y complejidad, lo calculable con lo calculable de forma eficiente. La memcomputación es equivalente a la computación con máquinas de Turing no deterministas, por tanto, cumple con la tesis de Church-Turing (pero la computación real va más allá). Un memcomputador es más eficiente en algunos problemas que un ordenador «convencional», pero calcular, calcula exactamente lo mismo.

      1. En el artículo dejan como trabajo futuro ver si cumple con la tesis de Church-Turing; cito:
        «It is worth pointing out that, if we could prove that a UMM is not Turing-equivalent, some (Turing) undecidable problems, such as the halting problem [2], may find solution within our UMM paradigm, thus contradicting the Church-Turing hypothesis [2]. Although this is an intriguing–albeit unlikely– possibility, we leave its study for future work.»

        Por lo que he leído una UMM es una máquina de Turing con «infinitas CPUs» y trabajando sobre los reales. Todavía no me aclaro como encaja nada de eso con la realidad física.

        1. La equivalencia entre máquina de Turing determinista y máquina de Turing no determinista es un resultado clásico, ambas cumplen la tesis de Church-Turing.

          Lo que sugieren los autores es que una variante de la idea de la memcomputación se pueda explotar más allá. Pero no lo que ya tienen, sino algo inspirado en lo que ya tienen.

  2. Pero Francis, esa máquina necesita una energía exponencial para llevar a cabo el Sub Set problem en un tiempo polinómico, y tú, como físico , sabes perfectamente que eso es lo mismito que necesitar un tiempo polinómico; es decir, que el problema es exactamente el mismo, y que conseguir una energía polinómica tiene los mismos problemas que conseguir un tiempo polinómico.

    El trabajo de esta gente es muy interesante a la hora de mostrarnos la relación energía-tiempo (que a mi me parece apasionante por otra parte), pero estamos en las mismas. Piénsalo

    1. Gracias, Pedro, muy acertada la opinión de Aaronson. Aún así, te confieso que soy bastante aficionado a los memristores y memdispositivos (campo en el que hecho algunos pinitos). Así que mi opinión en este asunto siempre está más a favor que en contra.

  3. A esto me refería en (https://francis.naukas.com/2010/08/09/una-copa-de-cava-y-la-demostracion-de-p%E2%89%A0np-de-vinay-deolalikar/#comment-437675)

    No había leído esta entrada de la memcomputación cuando te contesté ahí. Yo diría que esto hace casi 20 años ya lo estudié; de nuevo no tiene mucho aparentemente. Recuerdo haber hecho algún ejercicio que solo con puertas XOR resolvía una máquina de Turing (no creo que fuera NP). Me quede con la idea de que toda MT se puede convertir en un circuito lógico (y por supuesto viceversa), ahora sí con un pilón de PLDs. Esto no significa que el resultado se obtenga con coste P (para un algorimo NP), significa que si quieres ahorrar tiempo tienes que gastar en dispositivos, el coste sigue siendo NP.

    1. Iñigo, en teoría de la complejidad computacional se trabaja con algoritmos abstractos. No influye nada si se pueden implementar en hardware con puertas lógicas, microcableados, a bajo nivel o en un lenguaje de alto nivel. Como mucho cambia la constante de complejidad, pero el coste computational (que es asintótico y por tanto independiente de la constante) no cambia.

      Por cierto, una puerta XOR o un circuito combinacional con puertas XOR tan complicado como quieras implementa siempre un problema de coste computational constante. No entiendo la frase «no creo que fuera NP». Otra cosa es un circuito secuencial. La lógica programada en los PLD suele ser lógica combinacional, luego su coste es constante; aunque hay algunos «PLD modernos» que incluyen algo de lógica secuencial, pero se llaman FPLS.

Deja un comentario