Una transformación sistemática que asigna instancias y soluciones de un problema o estructura en un dominio a instancias y soluciones en otro dominio de modo que se preserva o refleja la solvibilidad o propiedades esenciales.

Principio

Una reducción proporciona una construcción R y una reconstrucción o interpretación S tales que resolver R(x) en el dominio objetivo produce, mediante S, una solución para x en el dominio origen; las reducciones ordenan problemas por dificultad relativa o expresividad.

Demostración

En teoría de la computabilidad, una reducción many-one f mapea instancias x del lenguaje A a instancias f(x) del lenguaje B de modo que x∈A si y solo si f(x)∈B; así la decidibilidad de B implica la decidibilidad de A componiendo un decididor para B con f.

Aplicación incorrecta

Tratar cualquier mapeo entre problemas como una reducción sin verificar la preservación de la existencia o corrección de soluciones —por ejemplo, usar una codificación inyectiva que no permite reconstruir una solución válida en el dominio origen.

Consecuencia

Una reducción correcta transfiere resultados conocidos: dureza, decidibilidad/indecidibilidad o cotas de complejidad se trasladan de la meta al origen según las restricciones de la reducción (p. ej., reducciones en tiempo polinómico preservan implicaciones de pertenencia en tiempo polinómico).

Inversión

La relación inversa, cuando existe, es una reducción en la dirección opuesta; la ausencia de una reducción recíproca indica una asimetría en dificultad o expresividad entre dominios.

Límite

Las reducciones requieren especificar con precisión los recursos y transformaciones permitidos (tipo: many-one, Turing, tiempo polinómico, parsimoniosa, etc.); los mapeos que cambian el criterio de aceptación o dependen de pasos no constructivos quedan fuera del alcance.

Tensión semántica

Reducción vs equivalencia: una reducción muestra transformabilidad relativa pero no necesariamente equivalencia bidireccional; a menudo se confunden reducciones con isomorfismos cuando la bidireccionalidad no está demostrada.

Síntesis

La reducción es un puente constructivo: un mapeo computable o constructivo más una traducción de retorno válida que traslada la solvibilidad o propiedades estructurales de un dominio a otro bajo restricciones de recursos especificadas.