O que é um NP-completo em ciência da computação?

StackOverflow https://stackoverflow.com/questions/210829

Pergunta

O que é um problema NP-completo? Por que é um tema tão importante em ciência da computação?

Foi útil?

Solução

NP significa Não-determinístico polinomial tempo.

Isto significa que o problema pode ser resolvido em tempo polinomial usando uma máquina de Turing não-determinística (como uma máquina de Turing regular, mas incluindo também uma função não-determinista "escolha"). Basicamente, uma solução tem de ser testável no tempo poly. Se for esse o caso, e um problema NP conhecido podem ser resolvidos usando o problema dado com entrada modificado (um problema NP pode ser reduzida para o problema dado), em seguida, o problema é NP completa.

A principal coisa a tirar de um problema NP-completo é que ele não pode ser resolvido em tempo polinomial em qualquer forma conhecida. NP-Hard / NP-completo é uma forma de mostrar que certas classes de problemas não são resolvidos em tempo realista.

Edit: Como outros já mencionado, existem muitas vezes soluções de aproximação para problemas NP-completos. Neste caso, a solução aproximação geralmente dá uma aproximação ligada usando a notação especial que nos diz quão perto a aproximação é.

Outras dicas

O que é NP ?

NP é o conjunto de todos os problemas de decisão (perguntas com um sim ou nenhuma resposta ) para o qual os 'yes'-respostas podem ser verified em tempo polinomial (o (n k ) onde n é o tamanho do problema, e k é uma constante) por máquina de um determinista Turing . tempo polinomial é usado às vezes como a definição de rápido ou rapidamente .

O que é P ?

P é o conjunto de todos os problemas de decisão que podem ser resolvido em tempo polinomial por um máquina de Turing determinística . Uma vez que pode ser resolvido em tempo polinomial, eles também pode ser verificado em tempo polinomial. Portanto P é um subconjunto de NP.

O que é NP-Complete ?

Um problema x que está em NP também está em NP-Complete se e só se todos os outros problemas em NP pode ser rapidamente (ie. Em tempo polinomial) transformado em x.

Em outras palavras:

  1. x está em NP e
  2. Cada problema em NP é redutível para x

Então, o que faz com que NP-Completo tão interessante é que, se qualquer um dos problemas NP-completos era para ser resolvido rapidamente, então tudo NP problemas podem ser resolvidos rapidamente.

Veja também o cargo O que é "P = NP ?", e por que é uma pergunta tão famoso?

O que é NP-Hard ?

NP-Hard são problemas que são pelo menos tão duro como os problemas mais difíceis em NP. Note-se que os problemas NP-completos também são NP-hard. No entanto, nem todos os problemas NP-difíceis são NP (ou mesmo um problema de decisão), apesar de ter NP como um prefixo. Essa é a NP em NP-duro não significa não-determinístico de tempo polinomial . Sim, isso é confuso, mas a sua utilização está enraizada e improvável de mudança.

meios NP-completos algo muito específico e você tem que ter cuidado ou você vai ter a errada definição. Em primeiro lugar, um problema NP é um sim / não problema tal que

  1. Não é à prova de tempo polinomial para cada instância do problema com uma resposta "sim" que a resposta é "sim", ou (de forma equivalente)
  2. Não existe um algoritmo de tempo polinomial (possivelmente usando variáveis ??aleatórias) que tem uma probabilidade não nula de responder "sim" se a resposta a uma instância do problema é "sim" e vai dizer "não" 100% de o tempo se a resposta for "não". Em outras palavras, o algoritmo deve ter uma taxa de falso-negativo menor que 100% e sem falsos positivos.

Um problema X é NP-Completo se

  1. X está em NP e
  2. Para qualquer problema Y em NP, existe uma "redução" de Y para X: um algoritmo de tempo polinomial que transforma qualquer instância do Y em uma instância de X tal que a resposta para a Y-exemplo é "sim" se e somente se a resposta X-exemplo é "sim".

Se X é NP-completos e um algoritmo determinista, polinomial-time existe que pode resolver todas as instâncias do X corretamente (0% de falsos-positivos, 0% de falso-negativos), então qualquer problema em NP pode ser resolvido em determinista -tempo -polynomial (por redução de X).

Até agora, ninguém veio acima com tal algoritmo de tempo polinomial determinista, mas ninguém provou que não existem (há um milhão de dólares para qualquer um que pode fazer qualquer um: o é a P = NP problema ). Isso não significa que você não pode resolver um caso particular de um problema NP-Completo (ou NP-Hard). Significa apenas que você não pode ter algo que vai funcionar de forma confiável em todas as instâncias de um problema da mesma maneira que você poderia confiantemente tipo uma lista de inteiros. Você pode muito bem ser capaz de chegar a um algoritmo que vai funcionar muito bem em todas as instâncias práticos de um problema NP-Hard.

NP-Complete é uma classe de problemas.

A classe P consiste nos problemas que podem ser resolvidos em tempo polinomial . Por exemplo, eles podem ser resolvidos em O (N k ) para alguma constante k, onde n é o tamanho da entrada. Simplificando, você pode escrever um programa que será executado em razoável tempo.

A classe NP é constituída por aqueles problemas que são em tempo polinomial verificável . Isto é, se nos é dada uma solução potencial, então poderíamos verificar se a solução dada é correta em tempo polinomial.

Alguns exemplos são o booleano satisfiability (ou SAT) problema, ou o problema-ciclo hamiltoniano. Há muitos problemas que são conhecidos por estar na classe NP.

NP-Complete significa que o problema é pelo menos tão duro quanto qualquer problema em NP.

É importante ciência da computação porque foi provado que qualquer problema em NP pode ser transformado em outro problema em NP-completo. Isso significa que uma solução para qualquer problema um NP-completos é uma solução para todos os problemas NP.

Muitos algoritmos de segurança depende do fato de que existem soluções não conhecidos pela NP problemas difíceis. Ele iria ter um impacto significativo sobre a computação se uma solução foi encontrada.

Basicamente problemas do mundo podem ser categorizadas como

1) Unsolvable Problem 2) Problema intratável 3) Problema NP- 4) P-Problema

1) A primeira é nenhuma solução para o problema. 2) A segunda é o tempo exponencial necessidade (isto é O (2 ^ n) acima). 3) A terceira é chamado a NP. 4) O quarto é fácil problema.

P:. Refere-se a uma solução do problema de polinomial Tempo

NP: refere-se polinomial tempo ainda para encontrar uma solução. Não temos certeza de que não há solução polinomial tempo, mas uma vez que você fornecer uma solução, esta solução pode ser verificada no polinomial tempo.

NP Complete: refere-se em polinomial tempo nós ainda ainda para encontrar uma solução, mas pode ser verificada na polinomial Time. O problema NPC em NP é o problema mais difícil, então se pudermos provar que temos solução P para o problema NPC, em seguida, problemas NP que podem ser encontrados em solução P.

NP rígido: refere-se polinomial tempo é ainda de encontrar uma solução, mas com certeza não é capaz de ser verificada na polinomial Time. problema NP rígido ultrapassa NPC dificuldade.

É uma classe de problemas em que temos de simular todas as possibilidades para ter certeza de que temos a solução ideal.

Há um monte de bons heurística para alguns problemas NP-completos, mas eles são apenas um palpite na melhor das hipóteses.

Se você está procurando um exemplo de um problema NP-completo, então eu sugiro que você dê uma olhada 3-SAT .

A premissa básica é que você tem uma expressão em conjuntivo forma normal , que é uma forma de dizendo que você tem uma série de expressões unidos por RUP que todos devem ser verdadeiras: 

(a or b) and (b or !c) and (d or !e or f) ...

O problema 3-SAT é encontrar uma solução que satisfaça a expressão onde cada um dos OR-expressões tem exatamente 3 booleans ao jogo: 

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

Uma solução para este pode ser um (a = T, b = T, C = M, d = F). No entanto, nenhum algoritmo foi descoberto que vai resolver este problema no caso geral em tempo polinomial. O que isto significa é que a melhor maneira de resolver este problema é fazer essencialmente uma força bruta adivinhar-e-cheque e tentar combinações diferentes até encontrar um que funcione.

especial do que sobre o problema 3-SAT é que qualquer problema NP-completo pode ser reduzida a um problema de 3 sab Isto significa que se você pode encontrar um algoritmo de tempo polinomial para resolver este problema, então você get $ 1.000.000 , para não mencionar o respeito e admiração de cientistas da computação e matemáticos de todo o mundo.

Honestamente, Wikipedia pode ser o melhor lugar para procurar uma resposta para isso.

Se NP = P, então podemos resolver problemas muito difíceis muito mais rápido do que pensávamos que poderia antes. Se resolvermos apenas um problema NP-completo em P (polinomial) tempo, então ele pode ser aplicado a todos os outros problemas na categoria NP-Completo.

Precisamos algoritmos e problemas distintos. Nós escrever algoritmos para resolver problemas, e eles escala de uma certa maneira. Embora esta seja uma simplificação, vamos rotular um algoritmo com um 'P' se a escala é bom o suficiente, e 'NP' se não é.

É útil saber coisas sobre os problemas que estamos tentando resolver, em vez dos algoritmos que usamos para resolvê-los. Então, vamos dizer que todos os problemas que têm um algoritmo bem-scaling estão "em P". E os que têm um algoritmo de má-scaling estão "em NP".

Isso significa que um monte de problemas simples são "em NP" também, porque podemos escrever algoritmos ruins para resolver problemas fáceis. Seria bom saber que problemas em NP são os que realmente complicado, mas nós não queremos apenas dizer "é os que não encontraram um bom algoritmo para". Afinal, eu poderia vir acima com um problema (chamemos-lhe X) que eu acho que precisa de um algoritmo de super-incrível. I dizer ao mundo que o melhor algoritmo que eu poderia vir para cima com para resolver escalas X mal, e então eu acho que X é um problema muito difícil. Mas amanhã, talvez mais inteligente alguém que me inventa um algoritmo que resolve X e está em P. Portanto, esta não é uma boa definição de problemas difíceis.

Ao mesmo tempo, existem muitos problemas em NP que ninguém conhece um bom algoritmo para. Então, se eu pudesse provar que X é um certo tipo de problema: um onde um algoritmo bom para resolver X podia também ser usado, de alguma forma indireta, para dar uma boa algoritmo para todas outro problema em NP. Bem, agora as pessoas podem ser um pouco mais convencido de que X é um problema verdadeiramente complicado. E neste caso nós chamamos X NP-Completo.

As definições para NP problemas completos acima está correto, mas eu pensei que poderia cera lírico sobre a sua importância filosófica como ninguém abordou essa questão ainda.

Quase todos os problemas complexos que você vai vir para cima contra será NP completa. Há algo muito fundamental sobre esta classe, e que apenas parece ser computacionalmente diferente de problemas facilmente solucionáveis. Eles tipo de ter o seu próprio sabor, e não é tão difícil de reconhecê-los. Isto significa basicamente que qualquer algoritmo moderadamente complexo é impossível para você resolver exatamente -. Programação, otimização, embalagem, cobrindo etc

Mas nem tudo está perdido se um problema que você vai encontrar é NP completa. Há um campo vasto e muito técnico, onde as pessoas estudar algoritmos de aproximação, que lhe dará garantias para estar perto da solução de um problema NP completo. Alguns destes são garantias incrivelmente fortes - por exemplo, para 3sat, você pode obter uma garantia de 7/8 através de um algoritmo realmente óbvio. Mesmo melhor, na realidade, existem algumas heurísticas muito forte, que se destacam em dar grandes respostas (mas sem garantias!) Para estes problemas.

Note que dois problemas muito famosas - isomorfismo gráfico e de factoring - não são conhecidos por serem P ou NP.

Eu ouvi uma explicação, que é:" NP-completo é provavelmente uma das idéias mais enigmáticas no estudo de algoritmos. "NP" significa "tempo polinomial não determinístico," e é o nome para o que é chamado de uma classe de complexidade a que os problemas podem pertencer. A coisa importante sobre o NP classe de complexidade é que os problemas dentro dessa classe pode ser verified por um algoritmo de tempo polinomial. Como exemplo, considere o problema de coisas contagem. Suponha que há um monte de maçãs em uma mesa. O problema é "Quantas maçãs estão lá?" Está equipado com uma possível resposta, 8. Você pode verificar esta resposta em tempo polinomial, utilizando o algoritmo de, duh, contando as maçãs. Contando as maçãs acontece em O (n) (que é o Big-oh notação) tempo, porque leva um passo para contar cada maçã. Para n maçãs, você precisa de n passos. Este problema está na classe de complexidade NP.

Um problema é classificado como NP-completos se puder ser demonstrado que é tanto NP-Hard e verificável em tempo polinomial . Sem entrar muito profundamente na discussão de NP-Hard, basta dizer que há certos problemas para os quais não foram encontradas soluções de tempo polinomial. Ou seja, é preciso algo como n! (N fatorial) passos para resolvê-los. No entanto, se você está dado uma solução para um problema NP-Completo, você pode verificá-lo em tempo polinomial.

Um exemplo clássico de um problema NP-completo é O Caixeiro Viajante problema ".

O autor: ApoxyButt De: http://www.everything2.com/title/NP-complete

NP Problema: -

  1. problema NP são de tal problema que pode ser resolvido em tempo polinomial não-determinístico.
  2. algoritmo não determinístico operar em duas fases.
  3. Não determinista adivinhar fase && Non fase de verificação determinista.

tipo de Np Problema

  1. NP completa
  2. NP rígido

NP problema completa: -

1 Decisão Problema Um é chamado NP completa se tem seguintes duas propriedades: -

  1. Ele pertence à classe NP.
  2. Qualquer outro problema em NP pode ser transformado em P em tempo polinomial.

Alguns Ex: -

  • problema da Mochila
  • problema sub set sum
  • Vertex problema de cobertura

problemas NP-completos são um conjunto de problemas para cada um dos quais qualquer outro NP-problema pode ser reduzido em tempo polinomial, e cuja solução ainda pode ser verificada em tempo polinomial. Ou seja, qualquer problema NP pode ser transformado em qualquer um dos problemas NP-completos. - Informalmente, um problema NP-completo é um problema NP que é pelo menos tão "duro" como qualquer outro problema em NP.

um problema NP é aquele em que um algoritmo de computador que verifica uma solução pode ser criado em tempo polinomial.

um problema NP-completo é NP, mas também se você pode resolvê-lo em tempo polinomial (chamado P), então todos os problemas NP são P.

Portanto, obter crackin'.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top