A arte de provar a complexidade de algoritmos

A teoria da complexidade, grosseiramente falando, preocupa-se em classificar os problemas computacionais de acordo com a sua dificuldade, assim, existem problemas resolvidos em tempo polinomial e aqueles resolvidos em tempo exponencial. Daí, temos as classes dos problemas P, NP, NP-completos, NP-difíceis e vários outros.

Provar que um problema é mais difícil que outro uma vez que não se encontrou um algoritmo que o resolve em tempo polinomial, consiste em transformar um problema que já se sabe da sua dificuldade para que ele seja resolvido pelo problema que se deseja provar a NP-completude ou NP-dificuldade.

Continuar lendo