NP-hard

Carta Poco común · N.º 124773

En teoría de la complejidad computacional, la clase de complejidad NP-hard (o NP-complejo, o NP-difícil) es el conjunto de los problemas de decisión que contiene los problemas H tales que todo problema L en NP puede ser transformado polinomialmente en H. Esta clase puede ser descrita como aquella que contiene a los problemas de decisión que son como mínimo tan difíciles como un problema de NP. Esta afirmación se justifica porque si podemos encontrar un algoritmo A que resuelve uno de los problemas H de NP-hard en tiempo polinómico, entonces es posible construir un algoritmo que trabaje en tiempo polinómico para cualquier problema de NP ejecutando primero la reducción de este problema en H y luego ejecutando el algoritmo A. Asumiendo que el lenguaje L es NP-completo, 1. L está en NP 2. ∀L' en NP, L' ≤ L En el conjunto NP-Hard se asume que el lenguaje L satisface la propiedad 2, pero no la propiedad 1. La clase NP-completo puede definirse alternativamente como la intersección entre NP y…

Leer en Wikipedia · Imagen Ascánder, CC BY-SA 4.0