##  [Many-One-Reduzierbarkeit](/de/node/60170) 

 Definition

Eine Berechenbarkeitsrelation zwischen Entscheidungsproblemen A und B: A ist many-one-reduzierbar auf B, wenn es eine berechenbare Funktion f gibt, die Instanzen x auf f(x) abbildet, so dass x in A genau dann ist, wenn f(x) in B ist. Die Reduktion ist einzelaufrufend und nicht adaptiv.

 

 

 

 

 

 





## Prinzip

Prinzip

Das zentrale Prinzip ist die Erhaltung der Zugehörigkeit durch eine einzige effektiv berechenbare Transformation: eine berechenbare f liefert eine einheitliche, instanzweise Übersetzung von A-Instanzen in B-Instanzen, sodass die Lösung von B auf f(x) die Lösung von A auf x liefert, ohne weitere Anfragen oder Anpassungen.

 

 

 

 

 





## Demonstration

Demonstration

Das klassische Beispiel ist die Reduktion der Halte-Menge codierter Maschinen mit Eingaben auf eine zugeschnittene Sprache: man konstruiert f, das eine Codierung von Maschine M und Eingabe w in die Codierung einer Maschine M' transformiert, die genau dann hält, wenn M auf w hält; die Zugehörigkeit wird durch die berechenbare Transformation bewahrt.

 

 

 

 

## Fehlanwendung

Fehlanwendung

Many-one-Reduzierbarkeit mit Turing-Reduzierbarkeit zu verwechseln und damit adaptive oder multiple Orakelanfragen zuzulassen, oder nichtberechenbare Transformationen zu verwenden und dennoch many-one-Reduzierbarkeit zu behaupten.

 

 

 

 

 





## Konsequenz

Konsequenz

Wenn A ≤_m B gilt, liefert jede Entscheidungsprozedur für B durch Komposition mit f eine Entscheidungsprozedur für A; many-one-Reduzierbarkeit erzeugt Halbordnungen von Schwierigkeitgraden und ermöglicht Begriffe wie m-Vollständigkeit unter effektiven Übersetzungen.

 

 

 

 

## Umkehrung

Umkehrung

Kehrt man die Richtung um zu B ≤_m A, ändert sich die Härterichtung: Fallen beide Richtungen an, sind die Probleme m-äquivalent, doch wenn nur die umgekehrte Richtung gilt, kann man Algorithmen nicht durch eine einzige berechenbare Abbildung von A auf B übertragen.

 

 

 

 

 





## Abgrenzung

Abgrenzung

Gilt für Mengen oder Sprachen und für berechenbare Funktionen als Übersetzer; schließt zufällige, approximative oder nichtuniforme Reduktionen aus und erfasst keine Reduktionen, die zusätzliche Orakelabfragen oder ressourcenbeschränkte Rechnungen verwenden, sofern nicht ausdrücklich angegeben.

 

 

 

 

 





## Semantische Spannung

Semantische Spannung

Many-one-Reduzierbarkeit steht in Nähe zu One-One-Reduzierbarkeit und Truth-Table-Reduzierbarkeit: One-One verlangt injektive Übersetzer, Truth-Table erlaubt nicht-adaptive parallele Anfragen; diese Unterschiede beeinflussen Gradstrukturen und Vollständigkeitskriterien.

 

 

 

 

 





## Synthese

Synthese

Many-one-Reduzierbarkeit ist die nicht-adaptive, einzelne-Transformations-Form relativer Berechenbarkeit: eine berechenbare Funktion übersetzt Instanzen von A einheitlich in Instanzen von B und erhält die Zugehörigkeit, was eine robuste Reduktions- und Vollständigkeitsbegrifflichkeit unter effektiven Abbildungen liefert.