Solucionador Analógico Supera Computadores Digitais em Otimização NP-Difícil

Os computadores digitais atuais realizam a maioria das tarefas com eficiência. São ideais para certos cálculos, processamento de texto, navegação na web e artes gráficas. No entanto, como dependem de código binário — 0s e 1s — não são ideais para resolver todos os problemas.

A Computação Digital Atingiu Seu Limite

A computação digital quase atingiu seu potencial máximo, razão pela qual alguns matemáticos começaram a se interessar em reviver a computação analógica. Ela pode ajudar a avançar a computação além da estrutura digital.

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

O Que São Problemas NP-Difíceis?

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

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

Por Que Computação Analógica?

Computadores analógicos foram extremamente populares em meados do século XX. Toda grande administração e empresa preocupada com problemas de dinâmica possuía um enorme centro de computação analógica. Eram usados para lançar foguetes ao espaço, guiar armas em navios de guerra e simular dinâmica de aeronaves.

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

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, computadores analógicos subtraem tensões correspondentes a esses valores e fornecem imediatamente a saída correta.

Podem ser usados para operações em tempo real e computação simultânea. No caso de problemas analógicos, podem fornecer insights sobre os problemas e erros. E como não requerem quantização, são perfeitos para modulação/demodulação de sinais 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 assumiram o mercado nos anos 1980. Eram suficientemente flexíveis, rápidos e mais precisos na realização de tarefas gerais. À medida que algoritmos eficientes surgiram, seu desempenho melhorou ainda mais.

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

Mas computadores digitais, incluindo os modernos, não conseguem 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 solução(ões) é ótima. Garantir que não existe nenhuma solução melhor é tão difícil quanto o próprio problema.

Solucionador Analógico de Alto Desempenho

O novo sistema dinâmico de tempo contínuo pode resolver um problema essencial de otimização discreta, chamado MaxSAT. O método baseia-se 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. Implementar a abordagem em computadores digitais, por outro lado, requer o uso de algoritmo integrador de equações diferenciais ordinárias que discretiza as equações de tempo contínuo e as resolve passo a passo enquanto lida com erros.

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

Leia também: Fatos Mais Interessantes Sobre Computadores Quânticos

E como a abordagem usa características gerais, ela pode ser estendida a outros problemas de otimização também. Os pesquisadores planejam projetar e construir dispositivos baseados nesta nova abordagem.