Un solucionador analógico para encontrar la mejor solución para problemas NP-Hard

• Los investigadores crean un nuevo sistema que puede resolver un problema de optimización discreto por excelencia, llamado MaxSAT.
• Este solucionador analógico funciona mejor que las computadoras digitales y también puede extenderse a otros problemas de optimización.

Las computadoras digitales de hoy realizan bien la mayoría de las tareas. Son perfectos para ciertos cálculos, procesamiento de texto, navegación web y artes gráficas. Pero dado que se basan en código binario (0 y 1), no son ideales para resolver todos los problemas.

La computación digital casi ha alcanzado su máximo potencial, y es por eso que algunos matemáticos han comenzado a interesarse en revivir la computación analógica. Puede ayudar a hacer avanzar la computación más allá del marco digital.

Recientemente, investigadores de la Universidad de Notre Dame y la Universidad Babes-Bolyai, Rumania, desarrollaron un nuevo solucionador analógico que puede evaluar las mejores soluciones de problemas NP-difíciles.

Problema NP-difícil significa que no existe un algoritmo que pueda resolver el problema en tiempo polinomial. El tiempo necesario para llegar a la solución aumenta exponencialmente con el tamaño del problema. Por lo general, estos problemas están asociados con imágenes médicas, bioinformática, plegamiento de proteínas y programación.

Los investigadores probaron su solucionador analógico en una amplia gama de problemas NP-difíciles y encontraron que este nuevo método tiene el potencial de conducir a mejores soluciones en menos tiempo.

¿Por qué la informática analógica?

Las computadoras analógicas fueron extremadamente populares a mediados del siglo XX. Todas las grandes administraciones y empresas interesadas en problemas de dinámica tenían un centro informático analógico gigante. Se utilizaron para lanzar cohetes al espacio, guiar armas en acorazados y simular la dinámica de los aviones.

A diferencia de las computadoras digitales, las computadoras analógicas usan datos no discretos como voltaje, peso, velocidad, temperatura y presión. Y dado que utilizan valores continuos, son inmunes al ruido de cuantificación.

Las computadoras analógicas se pueden diseñar para resolver una variedad de problemas. Pueden realizar directamente operaciones matemáticas. Por ejemplo, para restar 8 de 3, las computadoras analógicas restan los voltajes que corresponden a esos valores y luego proporcionan inmediatamente la salida correcta.

Se pueden utilizar para operaciones en tiempo real y cálculo simultáneo. En caso de problemas analógicos, pueden proporcionar información sobre los problemas y errores. Y como no requieren cuantificación, son perfectos para la modulación / demodulación de la señal y el control del motor de alta velocidad.

Referencia:Nature Communications | doi:10.1038 / s41467-018-07327-2 | Universidad de Notre Dame

Sin embargo, las computadoras digitales se apoderaron del mercado en la década de 1980. Eran lo suficientemente flexibles, rápidos y más precisos en la realización de tareas generales. A medida que aparecieron algoritmos eficientes, su rendimiento mejoró aún más.

Una computadora AMF665D analógica antigua | Crédito de la imagen:Francis Massen / YouTube

Pero las computadoras digitales, incluidas las modernas, no pueden resolver problemas NP difíciles con grandes variables. La dificultad con la mayoría de los problemas de optimización es que no puede determinar si las soluciones son óptimas. Asegurarse de que no haya una solución mejor es tan difícil como el problema en sí.

Solucionador analógico de alto rendimiento

El nuevo sistema dinámico de tiempo continuo puede resolver un problema de optimización discreta por excelencia, llamado MaxSAT. El método se basa en un conjunto determinista de ecuaciones diferenciales ordinarias y una técnica heurística para predecir la probabilidad de que la solución óptima haya sido evaluada por el tiempo analógico t.

En los circuitos analógicos se elimina el cuello de botella de von Neumann:el circuito mismo actúa como procesador y memoria. La implementación del enfoque en computadoras digitales, por otro lado, requiere el uso de un algoritmo integrador de ecuaciones diferenciales ordinarias que discretiza las ecuaciones de tiempo continuo y las resuelve paso a paso mientras maneja los errores.

En forma digital, el solucionador no funciona de manera eficiente porque la dinámica desarrolla varios miles de ecuaciones diferenciales ordinarias acopladas, lo cual es un proceso de integración que requiere mucho tiempo.

Leer:Datos más interesantes sobre las computadoras cuánticas

Y dado que el enfoque usa caracteres generales, también puede extenderse a otros problemas de optimización. El investigador planea diseñar y construir dispositivos basados ​​en este nuevo enfoque.