Como provar que um problema é NP completo?

108

Tenho problemas com o agendamento. Preciso provar que o problema é NP completo. Quais podem ser os métodos para provar que é NP completo?

algorithm thetna
fonte
Leia "Redutibility Between Combinatorial Problems" por Karp.
Paul Hankin

Respostas:

146

Para mostrar que um problema é NP completo, você precisa:

Mostre que está em NP

Em outras palavras, com algumas informações C, você pode criar um algoritmo de tempo polinomial Vque verificará para cada entrada possível Xse Xestá em seu domínio ou não.

Exemplo

Prove que o problema de coberturas de vértices (isto é, para algum gráfico G, ele tem um conjunto de cobertura de vértices de tamanho ktal que cada aresta em Gtem pelo menos um vértice no conjunto de cobertura ?) Está em NP:

  • nossa entrada Xé algum gráfico Ge algum número k(isto é da definição do problema)

  • Considere nossas informações Ccomo "qualquer subconjunto possível de vértices no gráfico Gde tamanho k"

  • Então, podemos escrever um algoritmo Vque, dado G, ke C, retornará se aquele conjunto de vértices é uma cobertura de vértice para Gou não, em tempo polinomial .

Então, para cada gráfico G, se existe algum "possível subconjunto de vértices em Gde tamanho k" que é uma cobertura de vértice, então Gé em NP.

Observe que não precisamos encontrar Cem tempo polinomial. Se pudéssemos, o problema seria em `P.

Observe que o algoritmo Vdeve funcionar para todos G , para alguns C. Para cada entrada deve haver informações que possam nos ajudar a verificar se a entrada está no domínio do problema ou não. Ou seja, não deve haver uma entrada onde a informação não existe.

Prove que é NP Difícil

Isso envolve a obtenção de um problema NP-completo conhecido como SAT , o conjunto de expressões booleanas na forma:

(A ou B ou C) e (D ou E ou F) e ...

onde a expressão é satisfazível , ou seja, existe alguma configuração para esses booleanos, o que torna a expressão verdadeira .

Em seguida, reduza o problema NP-completo ao seu problema em tempo polinomial .

Isto é, dado alguma entrada Xpara SAT(ou qualquer problema NP-completo que você está usando), crie alguma entrada Ypara o seu problema, de modo que Xesteja no SAT se e somente se Yestiver no seu problema. A função f : X -> Ydeve ser executada em tempo polinomial .

No exemplo acima, a entrada Yseria o gráfico Ge o tamanho da cobertura do vértice k.

Para uma prova completa , você teria que provar ambos:

  • isso Xestá em SAT=> Yno seu problema

  • e Yno seu problema => Xem SAT.

A resposta de marcog tem um link com vários outros problemas NP-completos que você poderia reduzir ao seu problema.

Nota de rodapé: Na etapa 2 ( Prove que é NP-difícil ), reduzir outro problema NP-difícil (não necessariamente NP-completo) para o problema atual, uma vez que problemas NP-completos são um subconjunto de problemas NP-difíceis (que são também no NP).

Laila Agaev
fonte
7
Eu me pergunto se há dados faltando ou um raciocínio circular por trás disso. Quero dizer, como 'provar' que um problema está no NP sem referi- lo a outro problema que 'já está no NP'? É como dizer "é feito de ferro porque sua parte é conhecida como ferro", isso não é uma prova de ferro.
Hernán Eche
6
Pelo que me lembro, existe um teorema chamado teorema de Cook-Levin que afirma que SAT é NP-completo. Essa prova é um pouco mais complicada do que o que descrevi acima e não acho que posso explicá-la com minhas próprias palavras.
Laila Agaev
4
Para ser mais preciso, o teorema de Cook-Levin afirma que SAT é NP-completo: qualquer problema em NP pode ser reduzido em tempo polinomial por uma máquina de Turing determinística ao problema de determinar se uma fórmula booleana é satisfatória (SAT). Então essa é a peça que faltava sobre a qual você estava perguntando. Se você procurar o teorema na Wikipedia, há uma prova e você pode referenciar o teorema em sua prova. Dito isso, reduzir o SAT a um determinado problema é a maneira que me ensinaram a provar a NP-completude.
Laila Agaev
Então minha pergunta acaba sendo se o SAT poderia ser resolvido no polinômio ou seja, o problema P = NP .. Obrigado pela sua resposta.
Hernán Eche
Você poderia explicar por que não podemos reduzir um problema NP-difícil ao problema que queremos, na segunda etapa? Tem que ser um problema NP-completo?
MLT
23

Você precisa reduzir um problema NP-Completo ao seu problema. Se a redução pode ser feita em tempo polinomial, então você provou que seu problema é NP-completo, se o problema já estiver em NP, porque:

Não é mais fácil do que o problema NP-completo, pois pode ser reduzido a ele em tempo polinomial, o que torna o problema NP-Difícil.

Veja o final de http://www.ics.uci.edu/~eppstein/161/960312.html para mais.

Moinudin
fonte
2
+1 alguém que explica de forma compreensível. em vez de dizer um monte de referências a palavras-chave que mal entendo.
ColacX
22
A primeira frase é inversa: você precisa reduzir o problema NP-completo conhecido ao seu próprio problema. Isso mostra que seu problema é pelo menos tão difícil quanto o problema NP-completo conhecido. A parte (b) também está incorreta: se você encontrou a redução, então você já sabe que seu problema é NP-difícil; a única questão é se está em NP (alguns problemas, como o Problema da Halting, não estão). Se for NP-difícil e em NP, então é NP-completo (ou seja, "NP-completo" é mais específico do que "NP-difícil").
j_random_hacker
1
Eu não diria que a) leva a uma contradição, já que não sabemos que P! = NP.
Chiel ten Brinke de
8

Para provar que um problema L é NP-completo, precisamos seguir os seguintes passos:

  1. Prove que seu problema L pertence a NP (isto é, dada uma solução, você pode verificá-lo em tempo polinomial)
  2. Selecione um problema NP-completo conhecido L '
  3. Descreva um algoritmo f que transforma L 'em L
  4. Prove que seu algoritmo está correto (formalmente: x ∈ L 'se e somente se f (x) ∈ L)
  5. Prove que algo f é executado em tempo polinomial
Albert s
fonte
7

Primeiro, você mostra que está em NP em tudo.

Então você encontra outro problema que você já sabe que é NP completo e mostra como você reduz polinomialmente o problema NP Difícil ao seu problema.

Lagerbaer
fonte
Não. Você precisa mostrar que pode reduzir de um problema NP completo a seu problema NP para provar a integridade NP E provar que ele está em NP. NP difícil não entra nisso, a menos que você não possa provar isso em NP.
mrmemio29
6
  1. Familiarize-se com um subconjunto de problemas NP Complete
  2. Prove NP Hardness: Reduza uma instância arbitrária de um problema NP completo a uma instância do seu problema. Este é o maior pedaço do bolo e onde a familiaridade com os problemas NP Complete compensa. A redução será mais ou menos difícil dependendo do problema NP Complete que você escolher.
  3. Prove que seu problema está em NP: projete um algoritmo que possa verificar em tempo polinomial se uma instância é uma solução.
UmNyobe
fonte