Reducibilidad Many-One

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.