Reducción (complejidad)

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.

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\le B$, y se añade un subíndice en $\le$ 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{\le }_{p}B$.

Véase también

• Dinámica de sistemas
• Pensamiento sistémico
• Azar
• Complejidad biológica
• Efecto mariposa
• Fractal
• Inteligencia artificial
• Problema del viajante
• Anexo:Clases de complejidad
• Sistemas dinámicos
• Teoría del caos
• Teoría de sistemas
• Cibernética