O que está avançando mais rápido: hardware ou algoritmos?

• É impossível comparar esses dois tipos de avanço de forma geral.

• Mas, se limitarmos a análise a um algoritmo específico, a comparação pode ser possível.

• Tomando como referência o problema SAT (https://en.wikipedia.org/wiki/Boolean_satisfiability_problem), que determina se existe uma solução que satisfaça uma expressão dada, foi comparada a velocidade de evolução de algoritmos e hardware.

• No hardware, os itens comparados foram um Pentium III processor (467MHz) + 1.5GB RAM (representando 1999) e um Intel Xeon Silver 4112 CPU (2.60GHz) + 128GB RAM (representando 2019).

• A velocidade foi comparada medindo quantas instâncias, entre 200, podiam ser resolvidas em até 900 segundos.

• No caso do problema SAT, o avanço dos algoritmos é mais rápido que o avanço do hardware.

• "Quando o Maple SAT solver, conhecido em 2019 como o melhor algoritmo, foi executado em hardware de 1999, houve casos em que ele resolveu ligeiramente menos instâncias do que outros algoritmos. Os autores também não sabem a razão exata, mas especulam que alguma estrutura de dados específica usada por esse bom algoritmo talvez seja muito mais adequada ao hardware moderno."