Reducción (complejidad)
# 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.

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

