Reducción (complejidad)

En teoría de la computación y teoría de la complejidad computacional, una reducción es una transformación de un problema a otro problema. Dependiendo de la transformación usada, la reducción se puede utilizar para definir clases de complejidad en un conjunto de problemas.

Ejemplo de reducción de un problema de satisfacibilidad booleana a un problema de cobertura de vértices. Los vértices azules forman una cobertura que se corresponde con los valores verdaderos.

Intuitivamente, un problema ${\displaystyle A}$ es reducible a un problema ${\displaystyle B}$ si las soluciones de ${\displaystyle B}$ existen y dan una solución para ${\displaystyle A}$ siempre que ${\displaystyle A}$ tenga solución. Así, resolver ${\displaystyle A}$ no puede ser más difícil que resolver ${\displaystyle B}$. Normalmente, esto se expresa de la forma ${\displaystyle A\leq B}$, y se añade un subíndice en ${\displaystyle \leq }$ para indicar el tipo de reducción utilizada. Por ejemplo, se usa la letra ${\displaystyle p}$ como subíndice para indicar que la reducción puede realizarse en tiempo polinomial: ${\displaystyle A\leq _{p}B}$.