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 ${\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}$.

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

• Datos: Q1197709