Alguém pode dar um exemplo de contador disso?Se um problema estiver no NP, então não há algoritmo de tempo polinomial conhecido para resolvê-lo

Question

Existe algum algoritmo de tempo polinomial conhecido para resolver um problema que esse problema está no NP.Foi-me dito é falso, mas não consigo pensar em nenhum exemplo do contador agora.

Answer 1

NP é a classe de problemas de decisão onde qualquer instância com uma resposta "sim" tem uma prova de que a resposta é sim, que pode ser verificada no tempo polinomial.NP contém todos os problemas que são solucionáveis no tempo polinomial.Portanto, há muitos problemas no NP com algoritmos de tempo polinômios conhecidos.

Se você está falando sobre problemas completos de NP, isso é um assunto totalmente diferente.Há (neste momento no tempo) nenhum problema de np-completo com um algoritmo de tempo polinomial conhecido para resolvê-lo.

Alguém pode encontrar uma prova de que, por um problema NP-completo, não há problema NP-completo com um algoritmo de tempo polinomial para resolvê-lo - não apenas nenhum algoritmo conhecido, mas nenhum algoritm.

Por outro lado, alguém pode realmente encontrar um NP-completo que possa ser resolvido em tempo polinômio.É improvável.