Une relation de calculabilité entre problèmes de décision A et B : A est réductible many-one à B s'il existe une fonction calculable f transformant des instances x en f(x) telle que x appartient à A exactement lorsque f(x) appartient à B. La réduction est à appel unique et non adaptative.

Principe

La règle essentielle est la préservation de l'appartenance par une transformation effectivement calculable unique : une f calculable fournit une traduction uniforme, instance par instance, des instances de A vers celles de B de sorte que résoudre B sur f(x) résout A sur x sans autres requêtes ni adaptations.

Démonstration

L'exemple classique est de réduire l'ensemble d'arrêt des machines avec encodages d'entrée à un langage construit : produire f qui transforme un encodage d'une machine M et d'une entrée w en l'encodage d'une machine M' qui s'arrête trivialement si et seulement si M s'arrête sur w ; l'appartenance est préservée par la transformation calculable.

Mauvaise application

Confondre la réductibilité many-one avec la réductibilité de Turing et donc permettre des requêtes adaptatives ou multiples à un oracle, ou utiliser des transformations non calculables et prétendre pourtant à une réduction many-one.

Conséquence

Quand A ≤_m B, toute procédure de décision pour B fournit une procédure pour A en la composant avec f ; la réductibilité many-one induit des ordres partiels de degrés de difficulté et permet des notions de complétude (m-complétude) sous translations effectives.

Inversion

Inverser la direction vers B réductible à A (B ≤_m A) change la notion de difficulté : si les deux directions tiennent alors les problèmes sont m-équivalents, mais si seule la direction inverse tient on ne peut pas transférer d'algorithmes de A à B par une unique traduction calculable.

Limite

S'applique à des ensembles ou langages et à des fonctions calculables comme traducteurs ; exclut les réductions aléatoires, approximatives ou non uniformes, et ne couvre pas les réductions utilisant des requêtes supplémentaires à un oracle ou des calculs limités en ressources sauf mention contraire.

Tension sémantique

La réductibilité many-one est proche de la one-one et de la truth-table : one-one exige des traducteurs injectifs, truth-table permet des requêtes non adaptatives en parallèle ; ces distinctions affectent la structure des degrés et les critères de complétude.

Synthèse

La réductibilité many-one est la notion non adaptative, à transformation unique, de calculabilité relative : une fonction calculable traduit uniformément les instances de A en instances de B en préservant l'appartenance, fournissant une notion robuste de réduction et de complétude sous translations effectives.