Pesquisa · Mapa mental

NP-completo

Na teoria da complexidade computacional, os problemas NP-completos representam o 'cume' da dificuldade dentro da classe NP. São problemas para os quais, se encontrarmos uma solução rápida (em tempo polinomial), poderemos resolver rapidamente *todos* os problemas da classe NP. A grande questão é se tais soluções rápidas existem. Um exemplo clássico é o problema da soma de subconjuntos: dado um conjunto de números, existe um subconjunto não vazio cuja soma é zero? Verificar uma resposta é fácil, mas encontrar essa resposta eficientemente é o grande desafio. Compreender a NP-completude nos ajuda a focar esforços, evitando a busca infrutífera por algoritmos rápidos para problemas que, provavelmente, não os possuem.

Fonte: Wikipédia (pt)Texto didático por IAAtualizado em 02/10/2026

Pontos-chave

  • NP-completos são os problemas mais difíceis da classe NP.
  • Se um problema NP-completo for resolvido rapidamente, todos os problemas NP serão resolvidos rapidamente.
  • A verificação de soluções para problemas NP é fácil, mas encontrar a solução pode ser difícil.
  • O problema P versus NP investiga se problemas NP-completos podem ser resolvidos em tempo polinomial.
  • Conhecer problemas NP-completos evita a busca por algoritmos ineficientes.
01

O que são Problemas NP-Completos?

Imagem: Ascánder · BY-SA · Openverse

NP-completo é um subconjunto de NP, a classe de problemas de decisão cujas soluções podem ser verificadas em tempo polinomial. Uma forma equivalente de definir NP é como os problemas que podem ser resolvidos em tempo polinomial por uma Máquina de Turing não determinística. Um problema 'p' está em NP-completo se e somente se todos os outros problemas em NP puderem ser transformados em 'p' em tempo polinomial. Esses problemas são cruciais porque a facilidade de verificar uma solução (NP) parece ligada à capacidade de resolvê-la rapidamente (P). A questão P=NP, ainda sem resposta, pergunta se todos os problemas NP podem ser resolvidos rapidamente. Se um único problema NP-completo for resolvido rapidamente, todos os problemas NP também poderão.

02

Definição Formal

Um problema de decisão 'C' é considerado NP-completo se ele satisfaz duas condições: 1) 'C' pertence à classe NP, o que significa que uma solução candidata para 'C' pode ser verificada em tempo polinomial. 2) 'C' é NP-difícil, ou seja, qualquer problema em NP pode ser reduzido a 'C' em tempo polinomial. Se um problema satisfaz a segunda condição, ele é chamado de NP-difícil, independentemente de pertencer ou não a NP. Uma consequência direta é que, se descobrirmos um algoritmo de tempo polinomial para um problema NP-completo, poderemos resolver todos os problemas da classe NP em tempo polinomial.

03

História e o Problema P vs NP

O conceito de NP-completo foi introduzido por Stephen Cook em 1971. Na época, houve um intenso debate sobre se os problemas NP-completos poderiam ser resolvidos em tempo polinomial. Essa questão, conhecida como o problema P versus NP, permanece um dos maiores mistérios da matemática. O Clay Mathematics Institute oferece um prêmio de 1 milhão de dólares para quem provar que P=NP ou que P≠NP. Até hoje, ninguém conseguiu apresentar uma prova formal conclusiva.

04

Exemplos e Exemplos Notáveis

Na teoria dos grafos, o problema do isomorfismo de subgrafos é NP-completo. Dois grafos são isomorfos se um pode ser obtido do outro por uma simples renomeação de seus vértices. Curiosamente, o problema do isomorfismo de grafos em si é suspeito de não pertencer nem a P nem a NP-completo, embora esteja em NP. Isso ilustra problemas considerados difíceis, mas talvez não no nível de NP-completude. Uma estratégia comum para provar que um novo problema é NP-completo é demonstrar que ele pertence a NP e, em seguida, reduzir um problema NP-completo já conhecido a ele. Por isso, conhecer uma lista de problemas comprovadamente NP-completos é muito útil. Exemplos conhecidos incluem o problema da satisfatibilidade booleana (SAT) e o problema do caixeiro viajante (versão de decisão).

05

Estratégias para Resolver Problemas NP-Completos

Atualmente, todos os algoritmos conhecidos para resolver problemas NP-completos exigem tempo exponencial em relação ao tamanho da entrada. A busca por algoritmos mais eficientes para problemas NP-completos de tamanho arbitrário geralmente envolve abordagens como: algoritmos de aproximação (que encontram soluções próximas da ótima), heurísticas (que buscam boas soluções rapidamente, sem garantia de otimalidade) e algoritmos exatos com desempenho melhorado para casos específicos ou com uso de técnicas como branch and bound.

06

Tipos de Redução

A definição padrão de NP-completo utiliza a 'redução em tempo polinomial muitos-para-um'. Outro tipo é a 'redução de Turing em tempo polinomial'. Nesta última, um problema X é Turing-redutível a Y se, com uma sub-rotina que resolve Y em tempo polinomial, podemos construir um programa que resolve X em tempo polinomial, chamando a sub-rotina quantas vezes for necessário. A redução muitos-para-um tem a restrição de chamar a sub-rotina apenas uma vez. Se definirmos NP-completude usando reduções de Turing, o conjunto resultante de problemas não seria menor que o NP-completo original; se seria maior é uma questão em aberto.

Vídeos recomendados

Fontes consultadas

Continue pesquisando