¿Memcomputing realmente resuelve un problema de NP completo?

9

Me encontré con un artículo publicado en Science "Memcomputing NP-complete problems in polinomial time usando recursos polinomiales y estados colectivos" , que hace algunas afirmaciones bastante sorprendentes.

Memcomputing es un paradigma de computación novedoso que no es de Turing que utiliza celdas de memoria interactivas (memprocessors para abreviar) para almacenar y procesar información en la misma plataforma física. Recientemente se demostró matemáticamente que las máquinas de computación de memoria tienen el mismo poder computacional que las máquinas de Turing no deterministas . Por lo tanto, pueden resolver problemas NP-completos en tiempo polinómico y, utilizando la arquitectura apropiada, con recursos que solo crecen polinomialmente con el tamaño de entrada.

(La cursiva es mía).

Descartaría esto de inmediato como no serio, dada la fuerte naturaleza de las afirmaciones, si no fuera por el hecho de que esto se publicó en Science, y que el material relacionado de algunos de los autores se publicó en Nature Physics , en una revista de IEEE y en Physics Review E , todas las cuales son publicaciones acreditadas revisadas por pares que no permitirían que tales afirmaciones se publiquen sin que sean serias.

¿Entonces es verdad? ¿Pueden estas personas resolver problemas NP-completos en tiempo P usando su modelo?

np-complete open-problem Alexander S King
fuente
1
La respuesta a la última pregunta es, por supuesto, no. La definición de P no cambió solo porque alguien inventó un nuevo y elegante modelo de computación.
Emil Jeřábek
@ EmilJeřábek no solo inventaron un nuevo modelo de cómputo, también afirmaron que es equivalente a NP.
Alexander S King el
3
Estás teniendo algo mezclado. Si hubieran demostrado que su modelo es equivalente a P, esto implicaría que P = NP.
Sasho Nikolov el
El resumen del artículo contiene la declaración: "Recientemente se demostró matemáticamente que las máquinas de computación de memoria tienen el mismo poder computacional que las máquinas de Turing no deterministas". Esto solo significa que los dos modelos pueden resolver los mismos problemas algorítmicos. No quiere decir que las complejidades de tiempo polinomiales se traduzcan nuevamente en complejidades de tiempo polinomiales.
Gamow
12
Ver chat.stackexchange.com/transcript/9446/2015/12/21 , especialmente scottaaronson.com/blog/?p=2212
Thomas Klimpel el

Respuestas:

9

Siento que esto ha sido respondido suficientemente en los comentarios, así que para resumir todo:

  • Los autores no reclaman P = NP, que es una declaración sobre máquinas de Turing deterministas y no deterministas.

  • Los autores proponen un modelo de computación que afirman que es equivalente en potencia a las máquinas de Turing no deterministas.

  • Los autores construyen máquinas físicas que implementan este modelo de computación para pequeños tamaños de entrada.

  • Los autores argumentan que construir versiones más grandes es físicamente realizable / posible con recursos de tamaño polinómico.

  • Esta última afirmación, que por supuesto no está probada y no es realmente una declaración formal, implicaría que, en general, es físicamente posible resolver problemas NP-completos con recursos de tamaño polinómico.

  • Scott Aaronson en una publicación de blog explica por qué este último reclamo es problemático y por qué la escalabilidad de su enfoque tiene problemas: http://www.scottaaronson.com/blog/?p=2212

usul
fuente
Me gustaría señalar que a partir de hoy (octubre de 2019), ni un solo investigador reprodujo el solucionador NP-completo de este artículo de 2015. Además, en todos los artículos subsiguientes relacionados con la computación en memoria de los mismos autores, no hubo una sola línea de código que ayude a reproducir el solucionador NP-complete.
G. Cohen