Quando falamos da complexidade de um problema, usamos frequentemente o termo “NP”. NP significa “nondeterministic polynomial time” (tempo polinomial não determinístico), que se refere à classe de problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing não determinística. Isto significa que o tempo necessário para resolver o problema aumenta no máximo polinomialmente à medida que o tamanho da entrada aumenta. No entanto, provar que um problema está em NP pode ser difícil. Neste artigo, vamos explorar como provar que um problema é NP e o que significa dizer que um problema é NP-completo. Também veremos porque é que as heurísticas são frequentemente utilizadas para resolver problemas NP-completos e como resolver o problema do caixeiro-viajante. Finalmente, vamos discutir o que é um algoritmo polinomial.
Para provar que um problema está em NP, temos de mostrar que uma solução para o problema pode ser verificada em tempo polinomial. Isto significa que, dada uma solução para o problema, podemos verificar se a solução está correcta ou não em tempo polinomial. Por exemplo, se tivermos uma solução para o problema do caminho hamiltoniano (ou seja, um caminho que visita cada vértice de um grafo exactamente uma vez), podemos verificar a solução verificando se é um caminho válido que visita cada vértice exactamente uma vez. Se pudermos verificar uma solução em tempo polinomial, então o problema está em NP.
Quando dizemos que um problema é NP-completo, queremos dizer que é um dos problemas mais difíceis em NP. De facto, todos os problemas em NP podem ser reduzidos a problemas NP-completos em tempo polinomial. Isto significa que se conseguirmos resolver um problema NP-completo em tempo polinomial, então podemos resolver qualquer problema em NP em tempo polinomial. Infelizmente, ainda ninguém foi capaz de encontrar um algoritmo em tempo polinomial para qualquer problema NP-completo. É por isso que as heurísticas são frequentemente usadas para resolver problemas NP-completos.
As heurísticas são algoritmos que não garantem uma solução óptima mas podem fornecer uma boa solução num período de tempo razoável. Por exemplo, para resolver o problema do caixeiro-viajante (ou seja, encontrar a rota mais curta possível que visita cada cidade exactamente uma vez), podemos utilizar um algoritmo heurístico como o algoritmo do vizinho mais próximo ou o algoritmo 2-opt. Estes algoritmos podem não nos dar o caminho mais curto absoluto, mas podem dar-nos uma boa aproximação do mesmo num período de tempo razoável.
Um algoritmo polinomial é um algoritmo que funciona em tempo polinomial. Isto significa que o tempo necessário para resolver o problema aumenta no máximo polinomialmente à medida que o tamanho da entrada aumenta. Por exemplo, se tivermos um algoritmo polinomial para o problema do caminho hamiltoniano, podemos resolver o problema em tempo polinomial para qualquer grafo. Infelizmente, ainda ninguém foi capaz de encontrar um algoritmo polinomial para qualquer problema NP-completo.
Em conclusão, provar que um problema está em NP envolve mostrar que uma solução para o problema pode ser verificada em tempo polinomial. Problemas NP-completos são os problemas mais difíceis em NP, e heurísticas são frequentemente usadas para resolvê-los. Um algoritmo polinomial é um algoritmo que corre em tempo polinomial, mas ainda ninguém conseguiu encontrar um algoritmo polinomial para qualquer problema NP-completo.