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

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

NP significa tempo polinomial não determinístico .

Isso significa que o problema pode ser resolvido no tempo polinomial usando uma máquina de Turing não determinística (como uma máquina de Turing comum, mas também incluindo uma função de "escolha" não determinística). Basicamente, uma solução deve ser testável em tempo poli. Se for esse o caso, e um problema NP conhecido puder ser resolvido usando o problema fornecido com entrada modificada (um problema NP pode ser reduzido ao problema especificado), então o problema está NP completo.

O principal a tirar de um problema NP-completo é que ele não pode ser resolvido no tempo polinomial de maneira conhecida. NP-Hard / NP-Complete é uma maneira de mostrar que certas classes de problemas não são solucionáveis ​​em tempo realista.

Edit: Como outros observaram, muitas vezes existem soluções aproximadas para problemas NP-Complete. Nesse caso, a solução aproximada geralmente fornece um limite de aproximação usando notação especial que nos diz o quão perto a aproximação está.

O que é NP ?

NP é o conjunto de todos os problemas de decisão (perguntas com resposta sim ou não) para os quais as respostas 'sim' podem ser verificadas em tempo polinomial (O (n ^k ) em que n é o tamanho do problema e k é um constante) por uma máquina determinística de Turing . Às vezes, o tempo polinomial é usado como a definição rápida ou rápida .

O que é P ?

P é o conjunto de todos os problemas de decisão que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística . Como eles podem ser resolvidos no tempo polinomial, eles também podem ser verificados no tempo polinomial. Portanto, P é um subconjunto de NP.

O que é NP-Complete ?

Um problema x que está no NP também está no NP-Complete se e somente se todos os outros problemas no NP puderem ser rapidamente transformados em x (isto é, em tempo polinomial) em x.

Em outras palavras:

1. x está em NP e
2. Todo problema no NP é redutível a x

Portanto, o que torna o NP-Complete tão interessante é que, se qualquer um dos problemas do NP-Complete fosse resolvido rapidamente, todos os problemas do NP poderiam ser resolvidos rapidamente.

Veja também o post O que é "P = NP?", E por que é uma pergunta tão famosa?

O que é o NP-Hard ?

NP-Hard são problemas que são pelo menos tão difíceis quanto os problemas mais difíceis do NP. Observe que os problemas NP-Complete também são difíceis de NP. No entanto, nem todos os problemas difíceis de NP são NP (ou mesmo um problema de decisão), apesar de terem NPcomo prefixo. Esse é o NP em NP-hard não significa tempo polinomial não determinístico . Sim, isso é confuso, mas é improvável que seu uso seja alterado.

NP-Complete significa algo muito específico e você deve ter cuidado ou poderá errar na definição. Primeiro, um problema de NP é um problema de sim / não, de modo que

1. Há uma prova de tempo polinomial para cada instância do problema com uma resposta "sim" de que a resposta é "sim" ou (equivalentemente)
2. Existe um algoritmo de tempo polinomial (possivelmente usando variáveis ​​aleatórias) que tem uma probabilidade diferente de zero de responder "sim" se a resposta para uma instância do problema for "sim" e dirá "não" 100% do tempo se a resposta é não." Em outras palavras, o algoritmo deve ter uma taxa de falso-negativo menor que 100% e nenhum falso-positivo.

Um problema X é NP-completo se

1. X está em NP e
2. Para qualquer problema Y em NP, há uma "redução" de Y para X: um algoritmo de tempo polinomial que transforma qualquer instância de Y em uma instância de X, de modo que a resposta para a instância Y seja "sim" se e somente se a resposta X-instance for "yes".

Se X é NP completo e existe um algoritmo determinístico de tempo polinomial que pode resolver todas as instâncias de X corretamente (0% de falsos positivos, 0% de falsos negativos), qualquer problema no NP pode ser resolvido em determinístico-polinomial- tempo (por redução para X).

Até agora, ninguém apresentou um algoritmo de tempo polinomial determinístico, mas ninguém provou que ele não existe (há um milhão de dólares para quem pode fazer isso: o problema é P = NP ). Isso não significa que você não pode resolver uma instância específica de um problema NP-Complete (ou NP-Hard). Significa apenas que você não pode ter algo que funcione de maneira confiável em todas as instâncias de um problema da mesma maneira que você poderia classificar de maneira confiável uma lista de números inteiros. É possível que você consiga criar um algoritmo que funcione muito bem em todas as instâncias práticas de um problema NP-Hard.

Basicamente, os problemas deste mundo podem ser classificados como

         1) Problema insolúvel 2) Problema intratável 3) Problema NP 4) Problema P

         1) O primeiro não é solução para o problema. 2) O segundo é o tempo exponencial necessário (ou seja, O (2 ^ n) acima). 3) O terceiro é chamado de NP. 4) O quarto é um problema fácil.

P: refere-se a uma solução do problema do tempo polinomial.

NP: refere-se ao tempo polinomial ainda para encontrar uma solução. Não temos certeza de que não há solução de horário polinomial, mas depois que você fornece uma solução, essa solução pode ser verificada no horário polinomial.

NP Complete: refere-se ao tempo polinomial ainda para encontrar uma solução, mas pode ser verificado no tempo polinomial. O NPC com problema no NP é o problema mais difícil, portanto, se pudermos provar que temos solução P para o problema NPC, problemas NP que podem ser encontrados na solução P.

NP Hard: refere-se ao tempo polinomial ainda para encontrar uma solução, mas com certeza não pode ser verificado no tempo polinomial. NP Hard problem ultrapassa a dificuldade NPC.

NP-Complete é uma classe de problemas.

A classe Pconsiste nos problemas que são solucionáveis ​​no tempo polinomial . Por exemplo, eles poderiam 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 tempo razoável .

A classe NPconsiste nos problemas que são verificáveis em tempo polinomial. Ou seja, se recebermos uma solução em potencial, poderíamos verificar se a solução fornecida está correta no tempo polinomial.

Alguns exemplos são o problema de Satisfação Booleana (ou SAT ) ou o problema do ciclo Hamiltoniano. Sabe-se que existem muitos problemas na classe NP.

NP-Completesignifica que o problema é pelo menos tão difícil quanto qualquer problema no NP.

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

Muitos algoritmos de segurança dependem do fato de que não existem soluções conhecidas para problemas difíceis do NP. Definitivamente, teria um impacto significativo na computação se uma solução fosse encontrada.

É uma classe de problemas em que precisamos simular todas as possibilidades para garantir a solução ideal.

Existem muitas heurísticas boas para alguns problemas do NP-Complete, mas na melhor das hipóteses são apenas um palpite.

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

A premissa básica é que você tem uma expressão em forma normal conjuntiva , que é uma maneira de dizer que você tem uma série de expressões unidas por ORs que todas devem ser verdadeiras:

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

O problema do 3-SAT é encontrar uma solução que satisfaça a expressão em que cada uma das expressões OR possui exatamente 3 booleanos para corresponder:

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

Uma solução para essa pode ser (a = T, b = T, c = F, d = F). No entanto, nenhum algoritmo foi descoberto que resolverá esse problema no caso geral em tempo polinomial. O que isso significa é que a melhor maneira de resolver esse problema é fazer essencialmente uma adivinhação e verificação da força bruta e tentar combinações diferentes até encontrar uma que funcione.

O que há de especial no problema 3-SAT é que QUALQUER problema NP-completo pode ser reduzido a um problema 3-SAT. Isso significa que, se você puder encontrar um algoritmo de tempo polinomial para resolver esse problema, receberá US $ 1.000.000 , sem mencionar o respeito e a admiração dos cientistas da computação e matemáticos de todo o mundo.

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

Se NP = P, podemos resolver problemas muito difíceis muito mais rapidamente do que pensávamos antes. Se resolvermos apenas um problema NP-Complete em tempo P (polinomial), ele poderá ser aplicado a todos os outros problemas na categoria NP-Complete.

Precisamos separar algoritmos e problemas. Escrevemos algoritmos para resolver problemas, e eles são dimensionados de uma certa maneira. Embora isso seja uma simplificação, vamos rotular um algoritmo com um 'P' se a escala for boa o suficiente e 'NP' se não for.

É útil saber coisas sobre os problemas que estamos tentando resolver, em vez dos algoritmos que usamos para resolvê-los. Então, diremos que todos os problemas que possuem um algoritmo de escala adequada estão "em P". E aqueles que têm um algoritmo de baixa escala estão "em NP".

Isso significa que muitos problemas simples também estão "no NP", porque podemos escrever algoritmos ruins para resolver problemas fáceis. Seria bom saber quais problemas no NP são realmente complicados, mas não queremos apenas dizer "são para os quais não encontramos um bom algoritmo". Afinal, eu poderia encontrar um problema (chame de X) que acho que precisa de um algoritmo super incrível. Eu digo ao mundo que o melhor algoritmo que eu poderia criar para resolver mal as escalas X e, portanto, acho que X é um problema muito difícil. Mas amanhã, talvez alguém mais inteligente que eu invente um algoritmo que resolva X e esteja em P. Portanto, essa não é uma definição muito boa de problemas difíceis.

Mesmo assim, existem muitos problemas no NP para os quais ninguém conhece um bom algoritmo. Portanto, se eu pudesse provar que X é um certo tipo de problema: um em que um bom algoritmo para resolver X também poderia ser usado, de alguma maneira indireta, para fornecer um bom algoritmo para todos os outros problemas no NP. Bem, agora as pessoas podem estar um pouco mais convencidas de que X é um problema genuinamente complicado. E, neste caso, chamamos X NP-Complete.

As definições para os problemas completos de NP acima estão corretas, mas achei que poderia ser lírico sobre sua importância filosófica, já que ninguém abordou essa questão ainda.

Quase todos os problemas complexos que você enfrentará serão NP Complete. Há algo muito fundamental nessa classe e que parece ser diferente em termos computacionais de problemas facilmente solucionáveis. Eles meio que têm seu próprio sabor, e não é tão difícil reconhecê-los. Isso basicamente significa que qualquer algoritmo moderadamente complexo é impossível para você resolver exatamente - programação, otimização, empacotamento, cobertura etc.

Mas nem tudo está perdido se um problema que você encontrar for NP Complete. Existe um campo vasto e muito técnico em que as pessoas estudam algoritmos de aproximação, o que lhe dará garantias de estar próximo da solução de um problema completo de NP. Algumas dessas são garantias incrivelmente fortes - por exemplo, para a 3sat, você pode obter uma garantia 7/8 através de um algoritmo realmente óbvio. Ainda melhor, na realidade, existem algumas heurísticas muito fortes, que se destacam em fornecer ótimas respostas (mas não há garantias!) Para esses problemas.

Observe que dois problemas muito famosos - isomorfismo gráfico e fatoração - não são conhecidos por P ou NP.

Eu ouvi uma explicação, ou seja: "NP-Completeness é provavelmente uma das idéias mais enigmáticas no estudo de algoritmos." NP "significa" tempo polinomial não determinístico "e é o nome do que é chamado de classe de complexidade para O problema da classe de complexidade NP é que os problemas nessa classe podem ser verificadospor um algoritmo de tempo polinomial. Como exemplo, considere o problema de contar coisas. Suponha que haja um monte de maçãs em uma mesa. O problema é "Quantas maçãs existem?" Você recebe uma resposta possível, 8. Você pode verificar essa resposta em tempo polinomial usando o algoritmo de, duh, contando as maçãs. A contagem das maçãs acontece no tempo O (n) (que é a notação Big-oh), porque é preciso um passo para contar cada maçã. Para n maçãs, você precisa de n etapas. Esse problema está na classe de complexidade NP.

Um problema é classificado como NP-completo se for possível mostrar que é NP-Difícil e verificável em tempo polinomial. Sem aprofundar a discussão sobre o NP-Hard, basta dizer que existem certos problemas para os quais as soluções de tempo polinomial não foram encontradas. Ou seja, é preciso algo como n! (n fatorial) etapas para resolvê-los. No entanto, se você tiver uma solução para um problema NP-Complete, poderá verificá-la em tempo polinomial.

Um exemplo clássico de um problema NP-Complete é o The Travelling Salesman Problem ".

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

NP Problema: -

1. Os problemas NP são problemas que podem ser resolvidos em tempo polinomial não determinístico.
2. O algoritmo não determinístico opera em dois estágios.
3. Fase de adivinhação não determinística && Fase de verificação não determinística.

Tipo de problema Np

1. NP completo
2. NP Hard

NP Problema completo: -

1 Decisão O Problema A é chamado NP completo se tiver as seguintes duas propriedades: -

1. Pertence à classe NP.
2. Todos os outros problemas no NP podem ser transformados em P no tempo polinomial.

Alguns Ex: -

• Problema da mochila
• problema de soma do subconjunto
• Problema de cobertura de vértices

Problemas completos de NP são um conjunto de problemas nos quais qualquer outro problema de NP pode ser reduzido no tempo polinomial e cuja solução ainda pode ser verificada no tempo polinomial. Ou seja, qualquer problema de NP pode ser transformado em qualquer um dos problemas de NP-completo. - Informalmente, um problema NP-completo é um problema NP que é pelo menos tão "difícil" quanto qualquer outro problema no NP.

Tanto quanto eu entendo

P é o conjunto de problemas que poderiam ser resolvidos em tempo polinomial com uma MT determinística.

NP é o conjunto de problemas que requer uma MT não determinística para ser resolvida em tempo polinomial. Isso significa verificar paralelamente todas as variáveis ​​possíveis, cada instância levando tempo polinomial. Se o problema for solucionável, pelo menos um desses estados paralelos deve ter a solução para o problema. Isso também significa que se você adivinhou as variáveis ​​da solução, a única coisa necessária é verificar a validade da solução em tempo polinomial.

NP-Hard é o conjunto em que os problemas são pelo menos tão difíceis quanto NP. Qualquer problema no NP pode ser transformado no problema NP-Hard em tempo polinomial. Esses problemas não podem ser resolvidos no tempo polinomial se P não for igual a NP. É quando o problema mais difícil em NP é solucionável em tempo polinomial, apenas os problemas em NP-Difícil são solucionáveis ​​em tempo polinomial.

NP-Complete é o conjunto de interseção de NP e NP-Hard. Qualquer problema NP pode ser transformado em um problema NP-Complete em tempo polinomial. Isso significa que se algum dos NP-Complete pudesse ter uma solução eficiente, qualquer problema de NP poderia ser resolvido com a mesma eficiência.

Por favor, deixe-me saber se eu cometi algum erro.

um problema de 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ê puder resolvê-lo em tempo polinomial (chamado P), todos os problemas de NP serão P.

Então, fique louco.