NP-Completeness
Un problema NP-completo pertenece a NP y todo problema de NP se reduce a él en tiempo polinómico; son los problemas más difíciles de NP.
Propósito
Comprender la jerarquía de complejidad y reconocer los problemas intratables.
Mecanismo
NP: verificable en tiempo polinómico. NP-difícil: todo problema de NP se reduce a él. NPC=NP∩NP-difícil. Si algún problema NPC tuviera solución polinómica, entonces P=NP. Clásicos: SAT, TSP, recubrimiento por vértices.
Casos de uso
- Análisis de complejidad
- Evaluación de la dificultad de problemas
- Pruebas por reducción