Aprendizaje automático Zhou Zhihua ¿Qué significa p=np?

El nombre completo en inglés de NP es Problema del polinomio no determinista.

Es decir, un problema no determinista con complejidad polinomial.

Problemas tipo P: Todos los problemas deterministas que pueden resolverse en tiempo polinomial constituyen problemas tipo P.

Problema determinista: El tema de investigación de determinar si existe un algoritmo que puede resolver un determinado tipo de problema.

Problemas de tipo NP: Todos los problemas de toma de decisiones que son solucionables en tiempo polinómico no determinista constituyen problemas de tipo NP.

Algoritmos no deterministas: Los algoritmos no deterministas descomponen el problema en dos etapas: adivinación y verificación.

Problema NPC: La complejidad de ciertos problemas en NP está relacionada con la complejidad de toda la clase de problemas. Todos los problemas NP se pueden resolver en tiempo polinomial si existen algoritmos de tiempo polinomial para estos problemas. Estos problemas se denominan problemas NP-completos (problemas NPC).