o problema de P envelhecido versus NP
então o que é então, o problema de P versus NP?
para o registro, o status quo é que P≠NP.
P (tempo polinomial) refere-se à classe de problemas que podem ser resolvidos por um algoritmo em tempo polinomial. Problemas na classe P podem variar de qualquer coisa tão simples quanto multiplicação para encontrar o maior número em uma lista. São o conjunto de problemas relativamente “mais fácil”.
NP (tempo polinomial não-determinístico) refere-se à classe de problemas que podem ser resolvidos em tempo polinomial por um computador não-determinístico., Esta é essencialmente uma outra maneira de dizer “Se eu tenho poder computacional ilimitado (ou seja, tantos computadores quanto eu preciso), Eu sou capaz de resolver qualquer problema no máximo tempo polinomial”. Mais intuitivamente, porém, refere-se à classe de problemas que atualmente, não tem forma de encontrar uma resposta rápida (tempo polinomial) suficiente, mas pode ser rapidamente verificada (em tempo polinomial) se a pessoa fornece a solução para o problema. O termo verificado aqui significa que se é capaz de verificar se a solução fornecida é realmente correta.
claramente, com base na definição acima, P ⊆ NP., Vamos dar uma olhada em um exemplo para ilustrar este problema abstrato.
Um dos exemplos mais comuns e eficazes é Sudoku. Dada uma grade de Sudoku não solucionada (9 x 9, por exemplo), seria necessário um algoritmo uma quantidade razoável de tempo para resolver uma. No entanto, se a grade 9 x 9 aumenta para uma grade 100 x 100 ou 10,000 x 10,000, o tempo que levaria para resolvê-la aumentaria exponencialmente porque o problema em si se torna significativamente mais difícil., No entanto, dada uma grade de Sudoku resolvida (de 9 x 9), é bastante simples verificar que a solução em particular é realmente correta, mesmo que as escalas de tamanho para 10,000 por 10,000. Seria mais lento, mas o tempo para verificar uma solução aumenta a uma velocidade mais lenta (polinomialmente).
existem muitos outros problemas NP lá fora, incluindo o problema Knapsack e o problema dos vendedores ambulantes, e eles são semelhantes em que eles são difíceis de resolver, mas rápidos de verificar., O problema fundamental que estamos tentando resolver aqui é:
Será que ser capaz de reconhecer rapidamente respostas corretas NP significa que também há uma maneira rápida de encontrá-las?
Se isso (i.e. P=NP), isso pode mudar significativamente a forma como olhamos para estes problemas NP (porque isso significa que há uma maneira rápida de resolver todos esses problemas, só que não temos sido capazes de descobrir como, AINDA.se isto não for suficientemente complicado, vamos apimentar.,
entre estes problemas NP, existe um rei de todos os problemas que os pesquisadores chamam de problemas NP-completo. Formalmente, eles são um conjunto de problemas para cada um do que qualquer outro problema NP pode ser reduzido (abordado abaixo) em tempo polinomial e cuja solução ainda pode ser verificada em tempo polinomial. Isto significa que qualquer problema NP pode ser transformado em um problema NP-completo.
informalmente, eles são os” mais difíceis ” dos problemas NP., Assim, se qualquer problema NP-Completo pode ser resolvido em tempo polinomial, então todo problema NP-Completo pode ser resolvido em tempo polinomial, e todo problema em NP pode ser resolvido em tempo polinomial (i.e. P=NP). O exemplo mais famoso seria o problema dos vendedores ambulantes.
existe também um conjunto de problemas chamados problemas NP-difíceis., Estes problemas são pelo menos tão difíceis quanto os problemas NP, mas sem a condição que requer que seja resolvido em tempo polinomial. Isto sugere que os problemas NP-difíceis podem não ser necessariamente parte da classe NP. Um exemplo seria resolver um tabuleiro de xadrez — dado o estado de um tabuleiro de xadrez, é quase impossível dizer se um dado movimento no estado em questão, é de fato o movimento ideal. Formalmente, não existe algoritmo de tempo polinomial para verificar uma solução para um problema NP-difícil.,
se juntarmos os dois, um problema NP-completo implica que seja NP-difícil, mas um problema NP-difícil não implica que seja NP-completo.
a Definição de NP-Completude
Um problema L, é NP-Completo se:
- L é NP-Hard
- L pertence a NP
O diagrama abaixo (foco no lado esquerdo) deve tornar as coisas mais claras.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
Informalmente, um problema L1 pode ser reduzido a outro problema L2 se:
- Qualquer instância da L1 pode ser modelado como uma instância de L2
- A solução para o segundo fornece uma solução para o antigo e vice-versa
Para entender isso de forma intuitiva, pode-se pensar nele como tal:
Se L1 é redutível a L2, L1 deve ser de, NO máximo tão duro como L2. Inversamente, L2 deve ser pelo menos tão duro quanto L1.
matematicamente, isto é denotado como: L1 ≤p L2 (lido como “L1 é polinomialmente redutível a L2”).,
