Eu estava querendo relaxar para ir dormir, aí resolvi ler o Knuth porque não tem nada que me acalme mais que ler o Knuth. Mas eu li um mindfuck tão grande que nem sei se consigo dormir hoje.

O SAT é NP-Completo né? Para testar se uma fórmula é satisfiable, você vai precisar de muito, muito esforço computacional, possivelmente exponencial se P != NP.

MAS, e aí vem o mindfuck, e se você testar entradas aleatórias até uma delas resolver a fórmula? A gente pode calcular quantas entradas você precisa, na média, para chegar a um resultado.

E a média é 2 (dois).

Gente, dois. Na média, com dois testes você acha o resultado.

Absolutamente nenhum problema útil da vida prática você consegue resolver com 2 testes aleatórios, e ainda assim a média é dois. Significa que a grande parte, a maior parte do universo dos problemas são os problemas inúteis. As coisas que interessam são um cisco minúsculo no mundão dos problemas possíveis. Não sei se eu fico feliz ou triste com essa conclusão.