• O Problema
• A Solução
• Resumo

Se você passar o tempo em ou ao redor da comunidade de programação você provavelmente ouvi o termo “P versus NP” com freqüência. Infelizmente, mesmo muitos com formação formal em Ciência da computação têm uma fraca compreensão do conceito.

então aqui está uma explicação simples e concisa:

o problema

p vs. NP o problema P vs. NP pergunta se todo problema cuja solução pode ser verificada rapidamente por um computador também pode ser rapidamente resolvido por um computador., (Wikipedia)

So let’s figure what we mean by P and NP.

problemas P são facilmente resolvidos por Computadores, e problemas NP não são facilmente solucionáveis, mas se você apresentar uma solução potencial é fácil verificar se está correto ou não.

Como pode ver no diagrama acima, todos os problemas P são problemas NP. Isto é, se é fácil para o computador resolver, é fácil de verificar a solução. Então o problema P vs NP está apenas perguntando se estes dois tipos de problema são os mesmos, ou se eles são diferentes, ou seja, que existem alguns problemas que são facilmente verificados, mas não facilmente resolvidos.,

atualmente parece que P ≠ NP, o que significa que temos muitos exemplos de problemas para os quais podemos verificar rapidamente as respostas potenciais, mas que não podemos resolver rapidamente. Vejamos alguns exemplos:

• um vendedor ambulante quer visitar 100 cidades diferentes dirigindo, iniciando e terminando sua viagem em casa. Ele tem um fornecimento limitado de gasolina, então ele só pode dirigir um total de 10.000 quilômetros. Ele quer saber se pode visitar todas as cidades sem ficar sem gasolina., (da Wikipédia)
• um agricultor quer levar 100 melancias de massas diferentes para o mercado. Ela precisa de embalar as melancias em caixas. Cada caixa só pode conter 20 kg sem quebrar. O agricultor precisa de saber se 10 caixas serão suficientes para levar todas as 100 melancias para o mercado. (da Wikipédia)

todos estes problemas compartilham uma característica comum que é a chave para entender a intriga de P versus NP: para resolvê-los você tem que tentar todas as combinações.

a solução

é por isso que a resposta para o p vs., O problema da NP é tão interessante para as pessoas. Se alguém fosse capaz de mostrar que P é igual a NP, isso tornaria os problemas difíceis do mundo real triviais para computadores.

resumo

1. p vs. NP lida com a diferença entre os computadores serem capazes de resolver rapidamente problemas vs. apenas serem capazes de testar as soluções propostas para correcção.
2. Como tal, o problema P vs. NP é a busca de uma maneira de resolver problemas que requerem a tentativa de milhões, bilhões ou trilhões de combinações sem realmente ter que tentar cada uma.,resolver este problema teria efeitos profundos na computação e, portanto, na nossa sociedade.

Fev 7, 2017 — Added Wikipedia attributions.2 de Março de 2014-limpou algumas das explicações para evitar confusão.

notas