Quais são as diferenças entre NP, NP-completa e NP-duro?

https://stackoverflow.com/questions/1857244

13-09-2019
|

Pergunta

Quais são as diferenças entre o NP , NP-Completo e NP-Hard ?

Estou ciente de muitos recursos em toda a web. Eu gostaria de ler as suas explicações, ea razão é que pode ser diferente do que está lá fora, ou há algo que eu não estou ciente de.

Solução

Eu suponho que você está procurando definições intuitivas, já que as definições técnicas requerem algum tempo para entender. Primeiro de tudo, vamos lembrar um conceito necessária preliminar para entender essas definições.

problema de decisão :. Um problema com um Sim ou não resposta

Agora, vamos definir os classes de complexidade .

P

P é uma classe de complexidade que representa o conjunto de todos os problemas de decisão que podem ser resolvidos em tempo polinomial .

Isto é, dado um exemplo do problema, as sim atender ou não pode ser decidida em tempo polinomial.

Exemplo

Dado um grafo G conectado, pode seus vértices ser colorido usando duas cores de modo que nenhuma aresta é monocromática?

Algoritmo: começar com um vértice arbitrário, cor de vermelho e todos os seus vizinhos azul e continuar. Pare quando você correr para fora de vértices ou você é forçado a fazer uma vantagem ter tanto de seus endpoints ser da mesma cor.

NP

NP é uma classe de complexidade que representa o conjunto de todos os problemas de decisão para a qual os casos em que a resposta é "sim" têm provas que podem ser verificadas em tempo polinomial.

Isto significa que se alguém nos dá um exemplo do problema e um certificado (às vezes chamado de uma testemunha) para a resposta ser sim, podemos verificar que ele está correto em tempo polinomial.

Exemplo

Integer factorisation está em NP. Este é o problema que dada inteiros n e m, existe um número inteiro com f 1 < f < m, de tal modo que divide f n (f é um pequeno fator de n)?

Este é um problema de decisão porque as respostas são sim ou não. Se alguém nos mãos uma instância do problema (para que eles entregar-nos inteiros n e m) e um f inteiro com 1 < f < m, e afirmam que f é um fator de n (o certificado), podemos verificar a resposta em polinomial tempo , executando o n / f divisão.

NP-Completo

NP-Complete é uma classe de complexidade que representa o conjunto de todos os problemas X em NP para o qual é possível reduzir qualquer outro problema Y NP para X em tempo polinomial.

intuitivamente Isto significa que nós podemos resolver Y rapidamente se sabemos como resolver X rapidamente. Precisamente, Y é redutível a X, se houver um algoritmo de tempo f polinomial para transformar casos y de Y a instâncias x = f(y) de X em tempo polinomial, com a propriedade de que a resposta a y é sim, se e somente se a resposta para f(y) é sim.

Exemplo

3-SAT. Este é o problema em que nos é dado um conjunto (ANDs) de 3-cláusula disjunções (RUP), demonstrações da forma

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

onde cada x_vij é uma variável booleana ou a negação de uma variável a partir de uma lista predefinida (x_1, x_2, ... x_n) finito.

Pode-se mostrar que todo problema NP pode ser reduzido a 3-SAT . A prova disso é técnico e requer o uso da definição técnica de NP ( com base em máquinas de Turing não determinística ). Isto é conhecido como Cook teorema .

O que faz problemas NP-completos importante é que se um algoritmo de tempo polinomial determinista pode ser encontrada para resolver um deles, todo problema NP pode ser resolvido em tempo polinomial (um problema para governá-los todos).

NP-hard

Intuitively, estes são os problemas que são pelo menos tão duro como os problemas NP-completos . Note-se que os problemas NP-difíceis não tem que estar em NP e não tem que ser problemas de decisão .

A definição precisa aqui é que um problema X é NP-hard, se houver um problema Y NP-completos, de tal forma que Y é redutível a X em tempo polinomial .

Mas uma vez que qualquer problema NP-completo pode ser reduzido a qualquer outro problema NP-completos em tempo polinomial, todos os problemas NP-completos podem ser reduzidos para qualquer problema NP-hard em tempo polinomial. Então, se não houver uma solução para um problema NP-hard em tempo polinomial, há uma solução para todos os problemas NP em tempo polinomial.

Exemplo

O problema da parada é um problema NP-hard. Este é o problema que dado um P programa e I entrada, será que vai parar? Este é um problema de decisão, mas não está em NP. É claro que qualquer problema NP-completo pode ser reduzida a este. Como outro exemplo, qualquer problema NP-completo é NP-hard.

Meu problema NP-completo favorito é o problema Minesweeper .

P = NP

Este é o problema mais famoso em ciência da computação, e uma das mais importantes questões pendentes nas ciências matemáticas. Na verdade, o Instituto argila está oferecendo um milhão de dólares para a solução para o problema (de writeup no site da argila Stephen Cook é muito bom ).

É claro que P é um subconjunto de NP. A questão em aberto é se ou não problemas NP têm soluções de tempo polinomial deterministas. em grande parte, acredita-se que eles não fazem. Aqui está um artigo notável recente sobre o mais recente (e a importância) do problema P = NP: o Estado da P versus NP .

O melhor livro sobre o assunto é Computadores e Intratabilidade por Garey e Johnson .

Outras dicas

Eu estive olhando ao redor e ver muitos longas explicações. Aqui está um pequeno gráfico que pode ser útil para resumir:

Observe como dificuldade aumenta cima para baixo: qualquer NP podem ser reduzidos a NP-Completo , e qualquer NP-completa pode ser reduzido a NP-Hard , tudo em P (polinomial) tempo.

Se você pode resolver uma classe mais difícil de problema em P tempo, isso vai significar que você encontrou como resolver todos os problemas mais fáceis em P tempo (por exemplo, provando P = NP, se você descobrir como resolver qualquer NP problema completa no tempo P).

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

Notas sobre entradas Yes ou No:

problema * Um NP que é também P é solúvel em P tempo.
** Um NP-Hard problema que também é NP-Completo é verificável no tempo P.
*** problemas NP-completos (todos os quais formam um subconjunto de NP-hard) poderia ser. O resto do NP duro não é.

Eu também achei este diagrama bastante útil em ver como tudo estes tipos correspondem um ao outro (prestar mais atenção para a metade esquerda do diagrama).

Esta é uma resposta muito informal à pergunta feita.

Can 3233 ser escrita como o produto de dois outros números maior do que 1? Existe alguma maneira de andar por um caminho em torno de todos os Sete Pontes de Königsberg sem tomar qualquer ponte duas vezes? Estes são exemplos de perguntas que partilham um traço comum. Pode não ser óbvio como para determinar de forma eficiente a resposta, mas se a resposta for 'sim', então há uma curta e rápida para verificar a prova. No primeiro caso, um fatoração não trivial de 51; na segunda, um percurso para caminhar as pontes (ajustando as restrições).

A problema de decisão é uma coleção de perguntas com sim ou não respostas que variam apenas em um parâmetro. Dizem que o COMPOSTO problema = { "É n composto": n é um inteiro} ou EULERPATH = { "O G gráfico tem um caminho de Euler?": G é um gráfico finito}.

Agora, alguns problemas de decisão se prestam a eficiente, se não algoritmos óbvias. Euler descobriu um algoritmo eficiente para problemas como o "Sete pontes de Königsberg" mais de 250 anos atrás.

Por outro lado, há muitos problemas de decisão, não é óbvio como para obter a resposta - mas se você sabe alguma informação adicional, é óbvio como ir sobre provando que você tem a resposta certa. COMPOSTO é assim: divisão Trial é o algoritmo óbvio, e é lento: para fator de um número de 10 dígitos, você tem que tentar algo como 100.000 possíveis divisores. Mas se, por exemplo, alguém lhe disse que 61 é um divisor de 3233, a divisão longa simples é uma maneira eficiente de ver que eles estão corretos.

A classe de complexidade NP é a classe de problemas de decisão onde os 'sim' respostas têm curta para estado, rápida de verificar as provas. Como composto. Um ponto importante é que esta definição não diz nada sobre o quão difícil é o problema. Se você tem uma maneira correta e eficiente para resolver um problema de decisão, apenas escrever para baixo os passos na solução é suficiente prova.

pesquisa Algoritmos continua, e novos algoritmos inteligentes são criados o tempo todo. Um problema que você pode não saber como resolver de forma eficiente hoje pode vir a ter um eficiente (se não for óbvio) solução de amanhã. Na verdade, ele levou os investigadores até 2002 para encontrar uma solução eficiente para COMPOSITE! Com todos esses avanços, um realmente tem que pensar: É este pouco sobre ter provas curtas apenas uma ilusão? Talvez todas problema de decisão que se presta a provas eficientes tem uma solução eficiente? Ninguém sabe .

Talvez a maior contribuição para este campo veio com a descoberta de uma classe peculiar de problemas NP. Brincando com modelos de circuitos para a computação, Stephen Cook encontrou um problema de decisão da variedade NP que era comprovadamente tão duro ou mais difícil do que todas outro problema NP. Uma solução eficaz para o booleano satisfazibilidade problema poderiam ser usadas para criar uma eficiente solução para qualquer outro problema em NP. Logo depois, Richard Karp mostrou que uma série de outros problemas de decisão poderia servir ao mesmo propósito. Estes problemas, em certo sentido os "mais difíceis" problemas em NP, ficou conhecido como NP-completos problemas.

Claro, NP é apenas uma classe de problemas de decisão. Muitos problemas não são, naturalmente, declarou desta maneira: "encontrar os fatores de N", "encontrar o caminho mais curto no grafo G que as visitas cada vértice", "dar um conjunto de atribuições de variáveis ??que faz a seguinte expressão boolean true". Embora se possa informalmente talk sobre alguns desses problemas "estar NP", tecnicamente isso não faz muito sentido - eles não são problemas de decisão. Alguns desses problemas podem até ter o mesmo tipo de poder como um problema NP-completo: uma solução eficiente para esses problemas (não-decisão) levaria diretamente para uma solução eficiente para qualquer problema NP. Um problema como este é chamado NP-hard .

Além das outras grandes respostas, aqui está o esquema típico as pessoas usam para mostrar a diferença entre NP, NP-Complete, e NP-Hard:

enter descrição da imagem aqui

P (polinomial Time): Como próprio nome sugere, estes são os problemas que podem ser resolvidos em tempo polinomial

NP (Tempo não-determinístico-polinomial): Estes são os problemas de decisão que podem ser verificadas em tempo polinomial. Isso significa que, se eu afirmar que existe uma solução em tempo polinomial para um problema particular, você me pedir para provar isso. Então, eu vou dar-lhe uma prova de que você pode facilmente verificar em tempo polinomial. Este tipo de problemas são chamados problemas NP. Note-se que, aqui, não estamos falando sobre se existe uma solução em tempo polinomial para este problema ou não. Mas estamos falando de verificação da solução para um determinado problema em tempo polinomial.

NP-Hard: Estes são pelo menos tão duro como os problemas mais difíceis em NP. Se podemos resolver esses problemas em tempo polinomial, podemos resolver qualquer problema NP que podem eventualmente existir. Note-se que estes problemas não são necessariamente problemas NP. Isso significa que, nós maio / pode-não verificar a solução para esses problemas em tempo polinomial.

NP-Completo: Estes são os problemas que são ambos NP e NP-Hard. Isso significa que, se podemos resolver estes problemas, podemos resolver qualquer outro problema NP e as soluções para esses problemas pode ser verificado em tempo polinomial.

A maneira mais fácil de explicar P v. NP e tal, sem entrar em detalhes técnicos é comparar "problemas de palavra" com "vários problemas de escolha".

Quando você está tentando resolver um "problema palavra" você tem que encontrar a solução a partir do zero. Quando você está tentando resolver um "múltiplos problemas de escolha", você tem uma escolha: ou resolvê-lo como se fosse um "problema de palavra", ou tente ligar em cada uma das respostas dadas a você, e escolher a resposta candidato que se encaixa.

Muitas vezes acontece que um "problema de múltipla escolha" é muito mais fácil do que o correspondente "problema da palavra":. Substituindo as respostas candidatos e verificar se eles se encaixam pode exigir muito menos esforço do que encontrar a resposta certa a partir do zero

Agora, se nós concordaríamos o esforço que leva tempo polinomial "fácil", em seguida, a classe P consistiria em "problemas de palavras fáceis", ea classe NP consistiria em "problemas de múltipla escolha fáceis".

A essência da P v NP é a pergunta: "Existem vários problemas escolha fácil que não são fáceis como problemas de palavras"? Ou seja, existem problemas para os quais é fácil de verificar a validade de uma determinada resposta, mas encontrar essa resposta a partir do zero é difícil?

Agora que entendemos intuitivamente o que NP seja, temos que desafiar a nossa intuição. Acontece que existem "problemas de múltipla escolha" que, em certo sentido, são mais difíceis de todos eles: se a pessoa iria encontrar uma solução para um desses "mais difíceis de todos eles" problemas um seria capaz de encontrar uma solução para todos problemas NP! Quando Cook descobriu isso 40 anos atrás, ele veio como uma surpresa completa. Estes "mais difícil de todas" os problemas são conhecidos como NP-hard. Se você encontrar uma "solução do problema palavra" para um deles você iria encontrar automaticamente uma "solução do problema palavra" para cada "fácil problema de múltipla escolha"!

Finalmente, os problemas NP-completos são aqueles que são simultaneamente NP e NP-hard. Seguindo a nossa analogia, eles são simultaneamente "fácil como vários problemas de escolha" e "o mais difícil de todos eles como palavra problemas".

Eu penso que nós podemos responder-lhe muito mais sucinta. Eu respondi a questão relacionada , e copiar a minha resposta de lá

Mas, primeiro, um problema NP-hard é um problema para o qual não podemos provar que existe uma solução em tempo polinomial. NP-dureza de algum "problema-P" é geralmente comprovada através da conversão de um problema NP-hard já provado o "problema-P" em tempo polinomial.

Para responder o resto da pergunta, você primeiro precisa entender que problemas NP-hard também são NP-completos. Se um problema NP-hard pertence a definir NP, então é NP-completo. Para pertencem ao conjunto NP, um problema precisa ser

(i) um problema de decisão,
(Ii) o número de soluções para o problema devem ser finita e cada solução deverá ter um comprimento de polinomial, e
(Iii) dada uma solução comprimento polinomial, que deve ser capaz de dizer se a resposta para o problema é sim / não

Agora, é fácil ver que poderia haver muitos problemas NP-difíceis que não pertencem ao conjunto NP e são mais difíceis de resolver. Como um exemplo intuitivo, a otimização-versão do vendedor ambulante onde nós precisamos de encontrar uma agenda real é mais difícil do que a versão decisão do caixeiro viajante, onde só precisamos para determinar se um cronograma com comprimento <= k existe ou não.

problemas NP-completos são aqueles problemas que são NP-Hard e na classe de complexidade NP. Portanto, para mostrar que qualquer problema é NP-completo, você precisa mostrar que o problema é tanto em NP e que é NP-hard.

Os problemas que estão na classe de complexidade NP podem ser resolvidos não-determinística em tempo polinomial e uma solução possível (ou seja, um certificado) para um problema em NP podem ser verificados quanto à correção em tempo polinomial.

Um exemplo de uma solução não-determinística para o problema k-clique seria algo como:

1) aleatoriamente seleccione k nós de um gráfico

2) verificar que estes k nós formar uma clique.

A estratégia acima é polinomial no tamanho do gráfico de entrada e, por conseguinte, o problema k-clique é em NP.

Note que todos os problemas podem ser resolvidos de forma determinística em tempo polinomial também estão em NP.

Mostrando que um problema é NP-hard normalmente envolve uma redução de algum outro problema NP-hard para o seu problema usando um mapeamento de tempo polinomial: http://en.wikipedia.org/wiki/Reduction_ (complexidade)

Há muito legal respostas para esta questão em particular, então não há nenhum ponto de escrever a minha própria explicação. Então eu vou tentar contribuir com um excelente recurso sobre diferentes classes de complexidade computacional.

Para alguém que pensa que a complexidade computacional é apenas cerca de P e NP, aqui é o recurso exaustivo mais sobre os diferentes problemas de complexidade computacional . Além de problemas perguntado pelo OP, enumerou aproximadamente 500 diferentes classes de problemas computacionais com descrições agradáveis ??e também a lista de trabalhos de pesquisa fundamentais que descrevem a classe.

Pelo que entendi, um np-hard problema não é "mais difícil" do que um NP-completos problema. Na verdade, por definição, todo problema NP-completo é:

em NP
np-hard

- Intro. aos Algoritmos (3ed) por Cormen, Leiserson, Rivest e Stein, pg 1069

Encontre algum defintion interessante:

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow