História da nomenclatura das classes de complexidade

Os pesquisadores começaram a resolver alguns problemas de algoritmos e repararam que para alguns problemas, não se achava algoritmos que os resolvessem, como por exemplo, os problemas do ciclo hamiltoniano, da coloração de vértices e arestas.

Eles continuaram a pesquisa, e alguns pesquisadores começaram a transformar alguns problemas em outros, de tal forma que se um deles fosse resolvido o outro também seria. Esse processo é chamado de redução. Eles conseguiram apenas um progresso parcial, mostrando que os dois problemas não estão desvinculados. Se resolver um, o outro também será resolvido.

E como surgiram vários problemas equivalentes nas mesmas categorias, eles as nomearam da seguinte forma:

· P: São problemas que podem ser resolvidos em tempo polinomial.

· NP: Ninguém consegue resolver seus problemas em tempo polinomial, mas é possível verificá-los em tempo polinomial.

· NPC: São os problemas onde, se um for resolvido, os outros também serão. Mais tarde foi mostrado que se um problema NPC for resolvido toda a classe NP também será. Esses são os problemas mais difíceis de NP.

Existem alguns problemas que não foram classificados como NPC (como primos e isomorfismo de grafos, por exemplo), pois eles não conseguiram fazer uma redução, por exemplo, de caminho hamiltoniano para isomorfismo de grafos. Aos poucos estão provando que esses problemas estão em P.

· NP-dificil: Existem problemas que são muito difíceis, que não estão em NP. Para esses problemas, não foi encontrado nenhum certificado polinomial. Como por exemplo, os problemas que estão em co-NP e não se sabem se estão em NP. Outro exemplo seria o jogo de xadrez. Não se sabe se sua resolução está em NP. Se for encontrado um algoritmo para resolver um desses problemas, certamente será possível reduzir todos os problemas de NP a ele. Esses problemas são tão difíceis que sua resolução resolveria todos os problemas de NP.

· co-NP: são os problemas cujos complementares estão em NP.