Una relación de calculabilidad entre problemas de decisión A y B: A es reducible many-one a B si existe una función computable f que mapea instancias x a f(x) tal que x pertenece a A exactamente cuando f(x) pertenece a B. La reducción es de llamada única y no adaptativa.

Principio

La regla clave es la preservación de la pertenencia mediante una única transformación efectivamente calculable: una f computable proporciona una traducción uniforme, instancia a instancia, de instancias de A a instancias de B de modo que resolver B en f(x) resuelve A en x sin más consultas ni adaptaciones.

Demostración

El ejemplo clásico es reducir el conjunto de parada de máquinas con codificaciones de entrada a un lenguaje diseñado: construir f que transforme la codificación de una máquina M y entrada w en la codificación de una máquina M' que se detiene precisamente cuando M se detiene en w; la pertenencia se preserva por la transformación computable.

Aplicación incorrecta

Confundir la reducibilidad many-one con la reducibilidad de Turing, lo que permitiría consultas adaptativas o múltiples al oráculo, o usar transformaciones no computables y aún afirmar reducibilidad many-one.

Consecuencia

Cuando A ≤_m B, cualquier procedimiento de decisión para B produce uno para A componiéndolo con f; la reducibilidad many-one induce ordenaciones parciales de grados de dificultad y sustenta nociones de completitud (m-completitud) bajo traducciones efectivas.

Inversión

Invertir la dirección a B ≤_m A cambia la dirección de la dureza: si ambas direcciones se cumplen, los problemas son m-equivalentes, pero si solo se cumple la dirección inversa no se pueden transferir algoritmos de A a B mediante una única traducción computable.

Límite

Se aplica a conjuntos o lenguajes y a funciones computables como traductoras; excluye reducciones aleatorias, aproximadas o no uniformes, y no cubre reducciones que usan consultas adicionales a un oráculo o cálculos acotados en recursos salvo que se indique.

Tensión semántica

La reducibilidad many-one está cercana a la one-one y la truth-table: one-one requiere traductores inyectivos, truth-table permite consultas paralelas no adaptativas; las diferencias afectan la estructura de grados y los criterios de completitud.

Síntesis

La reducibilidad many-one es la noción no adaptativa, de transformación única, de calculabilidad relativa: una función computable traduce uniformemente instancias de A en instancias de B preservando pertenencia, proporcionando una noción robusta de reducción y completitud bajo mapeos efectivos.