¿Alguien puede dar un ejemplo de contador?Si un problema está en NP, entonces no hay algoritmo de tiempo polinomial conocido para resolverlo

Question

¿Hay algún algoritmo de tiempo polinomial conocido para resolver un problema que ese problema está en NP?Me dijeron que es falso, pero ahora no puedo pensar en ningún ejemplo de contador.

Answer 1

NP es la clase de problemas de decisión donde cualquier instancia con una respuesta "SÍ" tiene una prueba de que la respuesta es sí, que se puede verificar en el tiempo polinomial.NP contiene todos los problemas que son solucionables en el tiempo polinomial.Por lo tanto, hay muchos problemas en NP con algoritmos de tiempo polinomios conocidos.

Si está hablando de problemas completos de NP, eso es un asunto completamente diferente.Hay (en este momento en el tiempo) ningún problema de NP-completo con un algoritmo de tiempo polinomial conocido para resolverlo.

Alguien podría encontrar una prueba de que para un problema de NP-completo no hay un problema completo de NP-completo con un algoritmo de tiempo polinomial para resolverlo, no solo sin algoritmo conocido, sino sin algoritmo en absoluto.

Por otro lado, alguien podría encontrar un NP-Completo que se puede resolver en el tiempo polinomial.Sin embargo, es poco probable.