Um solucionador analógico para encontrar a melhor solução de problemas NP-difíceis

• Pesquisadores constroem um novo sistema que pode resolver um problema de otimização discreta quintessencial, chamado MaxSAT.
• Este solucionador analógico tem um desempenho melhor do que os computadores digitais e também pode ser estendido a outros problemas de otimização.

Os computadores digitais de hoje realizam bem a maioria das tarefas. Eles são perfeitos para determinados cálculos, processamento de texto, navegação na web e artes gráficas. Mas como eles dependem de código binário - 0s e 1s - eles não são ideais para resolver todos os problemas.

A computação digital quase atingiu seu potencial máximo e é por isso que alguns matemáticos começaram a se interessar em reviver a computação analógica. Pode ajudar a avançar a computação além da estrutura digital.

Recentemente, pesquisadores da University of Notre Dame e da Babes-Bolyai University, Romênia, desenvolveram um novo solucionador analógico que pode avaliar as melhores soluções de problemas NP-difíceis.

Problema NP-difícil significa que não há algoritmo que pode resolver o problema em tempo polinomial. O tempo necessário para chegar à solução aumenta exponencialmente com o tamanho do problema. Normalmente, esses problemas estão associados a imagens médicas, bioinformática, dobramento de proteínas e programação.

Os pesquisadores testaram seu solucionador analógico em uma ampla gama de problemas NP-difíceis e descobriram que esse novo método tem o potencial de levar a melhores soluções em menos tempo.

Por que computação analógica?

Os computadores analógicos eram extremamente populares em meados do século XX. Cada grande administração e empresa preocupada com problemas de dinâmica tinha um gigantesco centro de computação analógica. Eles foram usados ​​para lançar foguetes ao espaço, guiar armas em navios de guerra e simular a dinâmica de aeronaves.

Ao contrário dos computadores digitais, os computadores analógicos usam dados não discretos como voltagem, peso, velocidade, temperatura e pressão. E como usam valores contínuos, são imunes a ruídos de quantização.

Os computadores analógicos podem ser projetados para resolver uma variedade de problemas. Eles podem realizar operações matemáticas diretamente. Por exemplo, para subtrair 8 de 3, os computadores analógicos subtraem as tensões que correspondem a esses valores e fornecem imediatamente a saída correta.

Eles podem ser usados ​​para operações em tempo real e computação simultânea. No caso de problemas analógicos, eles podem fornecer informações sobre os problemas e erros. E como não requerem quantização, são perfeitos para modulação / desmodulação de sinal e controle de motores de alta velocidade.

Referência:Nature Communications | doi:10.1038 / s41467-018-07327-2 | Universidade de Notre Dame

No entanto, os computadores digitais conquistaram o mercado na década de 1980. Eles eram suficientemente flexíveis, rápidos e mais precisos na execução de tarefas gerais. Conforme algoritmos eficientes surgiam, seu desempenho ficava ainda melhor.

Um computador AMF665D analógico vintage | Crédito da imagem:Francis Massen / YouTube

Mas os computadores digitais, incluindo os modernos, não podem resolver problemas NP-difíceis com grandes variáveis. A dificuldade com a maioria dos problemas de otimização é que você não pode determinar se a (s) solução (ões) é (são) ótima (s). Garantir que não haja nenhuma solução melhor é tão difícil quanto o próprio problema.

Analog Solver com alto desempenho

O novo sistema dinâmico de tempo contínuo pode resolver um problema de otimização discreta quintessencial, chamado MaxSAT. O método se baseia em um conjunto determinístico de equações diferenciais ordinárias e uma técnica heurística para prever a probabilidade de que a solução ótima tenha sido avaliada pelo tempo analógico t.

Em circuitos analógicos, o gargalo de von Neumann é eliminado:o próprio circuito atua como processador e memória. A implementação da abordagem em computadores digitais, por outro lado, requer o uso de um algoritmo integrador de equações diferenciais ordinárias que discretiza as equações de tempo contínuo e as resolve passo a passo enquanto trata os erros.

Na forma digital, o solucionador não funciona de forma eficiente porque a dinâmica evolui vários milhares de equações diferenciais ordinárias acopladas, o que é um processo de integração demorado.

Leia:Fatos mais interessantes sobre computadores quânticos

E como a abordagem usa caracteres gerais, ela também pode ser estendida a outros problemas de otimização. O pesquisador planeja projetar e construir dispositivos com base nessa nova abordagem.