Algoritmos de ADN y completitud NP

21

¿Cuál es la relación entre los algoritmos de ADN y las clases de complejidad definidas usando las máquinas de Turing? ¿A qué corresponden las medidas de complejidad como el tiempo y el espacio en los algoritmos de ADN? ¿Se pueden usar para resolver casos de problemas NP-completos como TSP que las máquinas von Neumann no pueden resolver de manera factible en la práctica?

Aadita Mehra
fuente
2
Publiqué
Aaron Sterling el

Respuestas:

31

Respuesta de Soundbite: la computación de ADN no proporciona una varita mágica para resolver problemas de NP completo, a pesar de que algunos investigadores respetados en la década de 1990 pensaron por un tiempo que podría.

El experimento inaugural de computación de ADN se realizó en un laboratorio dirigido por el reconocido teórico de números Len Adleman. Adleman resolvió un pequeño problema de vendedor ambulante, un conocido problema de NP completo, y él y otros pensaron por un tiempo que el método podría ampliarse. Adleman describe su enfoque en este breve video , que me parece fascinante. El problema que encontraron fue que para resolver un problema de TSP de tamaño modesto, necesitarían más ADN que el tamaño de la Tierra. Habían descubierto una forma de ahorrar tiempo al aumentar la cantidad de trabajo realizado en paralelo, pero esto no significaba que el problema de TSP requiriera menos recursos exponenciales para resolver. Solo habían cambiado el costo exponencial de la cantidad de tiempo a la cantidad de material físico.

(Hay una pregunta adicional: si necesita una cantidad exponencial de maquinaria para resolver un problema, ¿requiere automáticamente una cantidad exponencial de tiempo, o al menos preprocesamiento, para construir la maquinaria en primer lugar? Dejaré ese problema a un lado, sin embargo)

Este problema general, que reduce el tiempo que requiere una computación a expensas de algún otro recurso, ha aparecido muchas veces en modelos de computación de inspiración biológica. La página de Wikipedia sobre computación de membranas (una abstracción de una célula biológica) dice que cierto tipo de sistema de membranas puede resolver problemas NP-completos en tiempo polinómico. Esto funciona porque ese sistema permite la creación de muchos subobjetos exponencialmente dentro de una membrana global, en tiempo polinómico. Bueno ... ¿cómo llega una cantidad exponencial de materia prima del mundo exterior y entra a través de una membrana con área de superficie constante? Respuesta: no se considera. No están pagando por un recurso que la computación de otra manera requeriría.

Finalmente, para responder a Anthony Labarre, quien se vinculó a un artículo que muestra AHNEP puede resolver problemas de NP completo en tiempo polinómico. Incluso hay un documento que muestra que los AHNEP pueden resolver 3SAT en linealhora. AHNEP = Aceptando la red híbrida de procesadores evolutivos. Un procesador evolutivo es un modelo inspirado en el ADN, cuyo núcleo tiene una cadena que en cada paso se puede cambiar por sustitución, eliminación o (importante) inserción. Además, un número arbitrariamente grande de cadenas está disponible en cada nodo, y en cada paso de comunicación, todos los nodos envían todas sus cadenas correctas a todos los nodos conectados. Entonces, sin costo de tiempo, es posible transferir cantidades exponenciales de información, y debido a la regla de inserción, las cadenas individuales pueden ser cada vez más grandes en el transcurso del cálculo, por lo que es un doble golpe.

Si está interesado en un trabajo reciente en biocomputación, realizado por investigadores que se centran en cálculos que son prácticos en el mundo real, puedo ofrecerle esta reseña del libro que escribí recientemente para SIGACT News, que trata brevemente sobre múltiples áreas.

Aaron Sterling
fuente
@ Aaron: ¡Gracias! Ahora tengo que ir y leer tu reseña.
Aadita Mehra el
No podría haberlo dicho mejor. Esto también es cierto para una serie de otras técnicas de resolución de problemas de inspiración biológica, como algoritmos genéticos y plegamiento de proteínas.
user834
66
@Aaron: Usted preguntó "si necesita una cantidad exponencial de maquinaria para resolver un problema, ¿requiere automáticamente una cantidad exponencial de tiempo, o al menos preprocesamiento, para construir la maquinaria en primer lugar?". La respuesta es definitivamente sí. La razón de esto es que hay una densidad máxima posible dentro de una región antes de formar un agujero negro (para evitar esto necesita ), lo que significa que el radio del sistema debe escalar proporcionalmente a la masa para evitar esto. El poder computacional se escala a lo sumo linealmente en la masa. (continuación)r>2solmetrodo2
Joe Fitzsimons
55
(continuación) Por lo tanto, su cantidad exponencial de maquinaria tiene un radio exponencial. Como no se puede señalizar más rápido que la luz, una señal de un lado a otro tarda exponencialmente mucho tiempo en llegar al otro lado, por lo que si toda la maquinaria contribuye a la respuesta, es imposible resolver el problema en menos de exponencial hora.
Joe Fitzsimons
@ Joe: Gracias. :-) ¿Estaría bien para mí citar parte de sus comentarios en una pregunta de seguimiento? Me interesan los formalismos que capturan declaraciones como "El poder computacional se escala a lo sumo linealmente en la masa". ¿Cuánta complejidad de Kolmogorov hay por pulgada cuadrada, etc.
Aaron Sterling
13

Esto depende mucho de su modelo.

En realidad, la computación de ADN sigue leyes físicas (no relativistas), por lo que puede simularse en una computadora cuántica. Por lo tanto, lo mejor que puede esperar es que pueda resolver problemas completos de BQP. Sin embargo, es muy poco probable que esto sea cierto (el ADN es bastante grande, por lo que la coherencia no es realmente un problema), por lo que, por simulación, es casi seguro P. Sin embargo, es importante tener en cuenta que esto es eficiencia en términos del número de átomos utilizados, y francamente, los átomos son lo suficientemente baratos como para que este número sea astronómico, haciendo una simulación práctica de un tubo de ensayo lleno de ADN fuera del ámbito de lo que actualmente es posible.

Como resultado, muchas personas eligen trabajar con modelos que se aproximan bastante bien a lo que sucede en la práctica, pero se rompen cuando se los lleva al extremo. Un ejemplo de esto es el modelo de mosaico abstracto, que resulta que es NEXP completo (ver el documento de Gottesman e Irani de FOCS el año pasado).

Joe Fitzsimons
fuente
¡Gracias por la idea inteligente de ver la computación de ADN como un sistema físico! Voy a ver el papel que ha vinculado. Gracias de nuevo.
Aadita Mehra el
@Aadita: No hay problema. Espero que sea útil.
Joe Fitzsimons el
1
El modelo de mosaico Wang no pretende modelar la dinámica física. Cuando se interpreta como una herramienta para predecir el estado futuro de un sistema físico, lo que hace un mosaico de Wang válido es predecir el estado más probable de un sistema en equilibrio termodinámico; es decir, la energía más baja. Pero la termodinámica no da idea de cuánto tiempo puede tomar un sistema para converger al equilibrio; para eso necesitas cinética. Muchos sistemas tienen un equilibrio termodinámico que se logra solo después del tiempo exponencial. Para "complejidad computacional física", use cinética, no termodinámica; por ejemplo, el modelo de ensamblaje de azulejos.
Dave Doty
@Dave: Gracias por la información. Debo admitir que soy bastante ignorante del área, y tal vez he formulado muy mal esa parte de la respuesta. No tenía la intención de afirmar que se creía que era un modelo de la dinámica.
Joe Fitzsimons
2

Esta es una respuesta parcial

Del artículo de Wikipedia que mencionó, los algoritmos de computación de ADN molecular que resuelven problemas de NP completo no prueban que los problemas de NP completo se puedan resolver en tiempo polinómico en máquinas secuenciales (suponiendo que en la práctica sea posible el tiempo polinómico). La computación de ADN puede considerarse una forma de computación paralela. Finalmente, desde el punto de vista de la teoría de la computabilidad, la computación de ADN no es más poderosa que las máquinas de Turing.

Mohammad Al-Turkistany
fuente
1

Este documento puede ser interesante para usted; por cierto, le agradecería que alguien pudiera aclarar la impactante declaración que constituye su título.

Anthony Labarre
fuente
2
Algunos problemas fuera de PTIME pueden resolverse mediante máquinas paralelas en tiempo polinómico. Esto no es paradójico, ya que PTIME habla sobre los problemas que puede resolver una clase particular de máquinas secuenciales en el tiempo polinómico.
Charles Stewart el
55
Traté de aclarar en la respuesta que he publicado.
Aaron Sterling el