Classes NP Hard e NP-Complete

Um problema está na classe NPC se for NP e for tão hardcomo qualquer problema no NP. Um problema éNP-hard se todos os problemas em NP são redutíveis em tempo polinomial a ele, mesmo que não esteja no próprio NP.

Se um algoritmo de tempo polinomial existir para qualquer um desses problemas, todos os problemas em NP seriam solucionáveis ​​em tempo polinomial. Esses problemas são chamadosNP-complete. O fenômeno da NP-completude é importante tanto por razões teóricas quanto práticas.

Definição de NP-Completude

Uma linguagem B é NP-complete se satisfaz duas condições

  • B está em NP

  • Cada A em NP é o tempo polinomial redutível a B.

Se um idioma satisfaz a segunda propriedade, mas não necessariamente a primeira, o idioma B é conhecido como NP-Hard. Informalmente, um problema de pesquisaB é NP-Hard se existe algum NP-Complete problema A que Turing reduz a B.

O problema em NP-Hard não pode ser resolvido em tempo polinomial, até P = NP. Se for provado que um problema é NPC, não há necessidade de perder tempo tentando encontrar um algoritmo eficiente para ele. Em vez disso, podemos nos concentrar no algoritmo de aproximação de projeto.

Problemas NP-Completos

A seguir estão alguns problemas NP-Completos, para os quais nenhum algoritmo de tempo polinomial é conhecido.

  • Determinar se um gráfico tem um ciclo hamiltoniano
  • Determinar se uma fórmula booleana é satisfatória, etc.

Problemas NP-Difícil

Os seguintes problemas são NP-difíceis

  • O problema de satisfatibilidade do circuito
  • Conjunto de capa
  • Capa de vértice
  • Problema do caixeiro viajante

Neste contexto, agora iremos discutir o TSP é NP-Completo

TSP é NP-completo

O problema do caixeiro viajante consiste em um vendedor e um conjunto de cidades. O vendedor deve visitar cada uma das cidades partindo de uma determinada e voltando para a mesma. O desafio do problema é que o caixeiro viajante quer minimizar a duração total da viagem

Prova

Provar TSP is NP-Complete, primeiro temos que provar que TSP belongs to NP. No TSP, encontramos um passeio e verificamos se ele contém cada vértice uma vez. Em seguida, o custo total das bordas do passeio é calculado. Por fim, verificamos se o custo é mínimo. Isso pode ser concluído em tempo polinomial. portantoTSP belongs to NP.

Em segundo lugar, temos que provar que TSP is NP-hard. Para provar isso, uma maneira é mostrar queHamiltonian cycle ≤p TSP (como sabemos que o problema do ciclo hamiltoniano é NPcompleto).

Presumir G = (V, E) para ser uma instância do ciclo hamiltoniano.

Portanto, uma instância do TSP é construída. Nós criamos o gráfico completoG' = (V, E'), Onde

$$ E ^ {'} = \ lbrace (i, j) \ dois pontos i, j \ em V \: \: e \: i \ neq j $$

Assim, a função de custo é definida da seguinte forma -

$$ t (i, j) = \ begin {cases} 0 & if \: (i, j) \: \ in E \\ 1 & caso contrário \ end {cases} $$

Agora, suponha que um ciclo hamiltoniano h existe em G. É claro que o custo de cada borda emh é 0 no G' como cada borda pertence a E. Portanto,h tem um custo de 0 no G'. Assim, se o gráficoG tem um ciclo hamiltoniano, então o gráfico G' tem um tour de 0 custo.

Por outro lado, assumimos que G' tem um tour h' de custo no máximo 0. O custo das arestas emE' estão 0 e 1por definição. Portanto, cada aresta deve ter um custo de0 como o custo de h' é 0. Portanto, concluímos queh' contém apenas bordas em E.

Assim, provamos que G tem um ciclo hamiltoniano, se e somente se G' tem um tour de custo no máximo 0. O TSP é NP-completo.