Dureza NP
En la teoría de la complejidad computacional , la dureza NP ( dureza de tiempo polinomial no determinista ) es la propiedad definitoria de una clase de problemas que son informalmente "al menos tan difíciles como los problemas más difíciles en NP ". Un ejemplo simple de un problema NP-difícil es el problema de suma de subconjuntos .
Una especificación más precisa es: un problema H es NP-difícil cuando todo problema L en NP puede reducirse en tiempo polinomial a H ; es decir, suponiendo que una solución para H toma 1 unidad de tiempo, la solución de H se puede usar para resolver L en tiempo polinomial. [1] [2] Como consecuencia, encontrar un algoritmo de tiempo polinomial para resolver cualquier problema NP-difícil daría algoritmos de tiempo polinomial para todos los problemas en NP. Como se sospecha que P≠NP , es poco probable que exista tal algoritmo. [3]
Se sospecha que no existen algoritmos de tiempo polinomial para problemas NP-difíciles, pero eso no ha sido probado. [4] Además, la clase P , en la que todos los problemas se pueden resolver en tiempo polinomial, está contenida en la clase NP . [5]
Un problema de decisión H es NP-difícil cuando para cada problema L en NP, hay una reducción de muchos a uno en tiempo polinomial de L a H . [1] : 80 Una definición equivalente es exigir que todo problema L en NP pueda resolverse en tiempo polinomial mediante una máquina de oráculo con un oráculo para H . [6] De manera informal, se puede pensar en un algoritmo que llame a una máquina oráculo como una subrutina para resolver H y resuelva L en tiempo polinomial si la llamada a la subrutina toma solo un paso para calcular.
Otra definición es requerir que haya una reducción de tiempo polinomial de un problema NP-completo G a H . [1] : 91 Como cualquier problema L en NP se reduce en tiempo polinomial a G , L se reduce a su vez a H en tiempo polinomial por lo que esta nueva definición implica la anterior. Torpemente, no restringe la clase NP-difícil a problemas de decisión, y también incluye problemas de búsqueda o problemas de optimización .
Algunos problemas de optimización NP-hard pueden aproximarse en tiempo polinomial hasta una relación de aproximación constante (en particular, aquellos en APX ) o incluso hasta cualquier relación de aproximación (aquellos en PTAS o FPTAS ).
