Polynomial Reduction
Una reducción polinomial convierte el problema A en el problema B en tiempo polinómico; si B es resoluble entonces A también lo es, y esto se usa para demostrar la NP-dificultad.
Propósito
Demostrar la dureza de los problemas y transferir la resolubilidad; una herramienta central de la teoría de la complejidad.
Mecanismo
A ≤_p B: existe una función f de tiempo polinómico que mapea instancias de A a instancias de B tal que A(x)=B(f(x)). Si B∈P entonces A∈P. Si A es conocido como NP-difícil y A≤_p B, entonces B es NP-difícil.
Casos de uso
- Demostraciones de complejidad
- Reducciones NP-difíciles
- Clasificación de problemas