NP-Completude e Intratabilidade

A NP-completude identifica os problemas mais difíceis na classe NP — aqueles aos quais todo problema NP se reduz — e fornece a estrutura padrão para reconhecer problemas para os quais nenhum algoritmo eficiente é conhecido ou provável.

Definition

Um problema de decisão é NP-completo se ele pertence a NP (suas instâncias 'sim' possuem certificados verificáveis eficientemente) e todo problema em NP se reduz a ele em tempo polinomial; tais problemas são os mais difíceis em NP, e um algoritmo de tempo polinomial para qualquer um resultaria em um para todos.

Scope

Este tópico abrange as classes de complexidade P e NP, reduções em tempo polinomial, as definições de NP-dureza e NP-completude, o teorema de Cook-Levin que estabelece a satisfatibilidade como NP-completa, o catálogo de problemas NP-completos de Karp e as consequências práticas da intratabilidade para o projeto de algoritmos. Aplica esses conceitos ao reconhecimento e manejo de problemas difíceis; a teoria formal mais ampla das classes de complexidade computacional é tratada no subcampo da teoria da computação.

Core questions

• O que distingue as classes de complexidade P e NP?
• Como uma redução em tempo polinomial transfere a dureza de um problema para outro?
• O que o teorema de Cook-Levin estabelece e por que a satisfatibilidade é central?
• Como um novo problema é provado NP-completo por redução de um já conhecido?
• Uma vez que um problema é mostrado NP-difícil, quais estratégias algorítmicas permanecem?

Key concepts

• classe de complexidade P
• classe de complexidade NP
• redução em tempo polinomial
• NP-dureza
• NP-completude
• teorema de Cook-Levin
• satisfatibilidade booleana (SAT)
• questão P versus NP

Key theories

Teorema de Cook-Levin

O teorema de Cook-Levin prova que a satisfatibilidade booleana (SAT) é NP-completa: todo problema em NP se reduz a ela em tempo polinomial, fornecendo o primeiro problema NP-completo e a âncora para provar a dureza de outros.

Redutibilidade entre problemas combinatórios

Karp mostrou que reduções em tempo polinomial ligam muitos problemas naturais — clique, cobertura de vértice, ciclo hamiltoniano, partição e outros — em uma rede de problemas NP-completos, de modo que cada um pode ser provado difícil por redução de outro.

Clinical relevance

Reconhecer que um problema é NP-completo é um dos resultados mais úteis na computação: ele informa aos engenheiros para não esperarem um algoritmo exato rápido e, em vez disso, implantarem algoritmos de aproximação, heurísticas, resolvedores exatos ajustados para instâncias típicas, ou restrições a casos especiais tratáveis. Muitos problemas de agendamento, roteamento, empacotamento e design são NP-completos.

History

Stephen Cook introduziu a NP-completude em 1971, provando que SAT é NP-completo; Leonid Levin alcançou resultados semelhantes independentemente. O artigo de Richard Karp de 1972 mostrou 21 problemas naturais NP-completos, estabelecendo o alcance da estrutura. O livro de Garey e Johnson de 1979 catalogou centenas de problemas NP-completos e tornou-se a referência padrão.

Debates

P versus NP

Se P é igual a NP — se todo problema eficientemente verificável é também eficientemente solúvel — é o problema aberto mais proeminente na área; quase todos os pesquisadores conjecturam que P não é igual a NP, mas a questão permanece sem solução e é um problema do Prêmio Millennium.

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Michael Garey
• David Johnson

Seminal works

• cook1971
• karp1972
• cormen2009

Frequently asked questions

Qual a diferença entre NP-difícil e NP-completo?

Um problema é NP-difícil se todo problema NP se reduz a ele em tempo polinomial, mas ele próprio não precisa estar em NP e não precisa ser um problema de decisão. Um problema é NP-completo se ele é tanto NP-difícil quanto está em NP. Problemas NP-completos são os problemas mais difíceis que ainda estão em NP.

NP-completude significa que um problema nunca pode ser resolvido?

Não. Significa que nenhum algoritmo de tempo polinomial é conhecido para todas as entradas e provavelmente nenhum existe se P não for igual a NP. Na prática, tais problemas são abordados com algoritmos de aproximação, heurísticas, resolvedores de tempo exponencial que funcionam em instâncias realistas, ou restringindo-se a casos especiais.