Trabalho complexidade computacional

Problemas clássicos de Complexidade Computacional

Canoas, 07 de Junho de 2013.
Introdução

A complexidade computacional procura estabelecer limites para a eficiência dos algoritmos, investigando a dificuldade inerente dos problemas computacionais. O problema P e NP é uma questão central em complexidade computacional. Inicialmente, ele procura determinar se, para uma classe importante de problemas computacionais, a busca exaustiva por soluções é essencialmente a melhor alternativa algorítmica possível.

A pesquisa em complexidade computacional pode ser dividida em dois grandes grupos P e NP

Pode-se estudar a dificuldade de um problema computacional especifico, ou investigar como certos recursos computacionais e classes de problemas estão relacionados. Apesar dessa divisão, o estudo de classes de problemas pode muitas vezes ser reduzido ao estudo de problemas individuais (completos) que capturam propriedades essenciais da classe.

A classe NP contêm os problemas computacionais com soluções que podem ser verificadas de forma eficiente. Intuitivamente, o problema P vs NP pergunta como essas duas classes estão relacionadas, ou seja, se para todo problema cujas soluções são eficientemente checáveis também existe um algoritmo eficiente capaz de encontrar tais soluções. Apesar de ser uma questão envolvendo classes de problemas, a existência de problemas completos para a classe NP torna interessante o estudo de alguns problemas computacionais específicos.

Dado um problema computacional pertencente à classe NP, existe um algoritmo muito simples capaz de resolvê-lo. Ele procede da seguinte forma: gera todas as respostas possíveis para uma dada instância do problema e então aplica um algoritmo capaz de checar essas respostas (a existência desse ultimo é garantida pela definição de NP). Uma desvantagem