Eine systematische Transformation, die Instanzen und Lösungen eines Problems oder einer Struktur in einer Domäne auf Instanzen und Lösungen in einer anderen Domäne abbildet, sodass Lösbarkeit oder wesentliche Eigenschaften erhalten bleiben oder widergespiegelt werden.

Prinzip

Eine Reduktion liefert eine Regel oder Konstruktion R und eine Rekonstruktion oder Interpretation S, so dass das Lösen von R(x) in der Zieldomäne mittels S eine Lösung für x in der Quelldomäne ergibt; Reduktionen ordnen Probleme nach relativer Schwierigkeit oder Ausdrucksfähigkeit.

Demonstration

In der Berechenbarkeitstheorie bildet eine many-one-Reduktion f Instanzen x der Sprache A auf Instanzen f(x) der Sprache B ab, so dass x∈A genau dann gilt, wenn f(x)∈B ; somit impliziert die Entscheidbarkeit von B die Entscheidbarkeit von A durch Komposition eines Entscheiders für B mit f.

Fehlanwendung

Jede Abbildung zwischen Problemen als Reduktion zu behandeln, ohne die Erhaltung der Existenz oder Korrektheit von Lösungen zu prüfen – etwa durch Verwendung einer injektiven Codierung, die keine Rekonstruktion einer gültigen Quelllösung erlaubt.

Konsequenz

Eine korrekte Reduktion überträgt bekannte Ergebnisse: Härte, Entscheidbarkeit/Unentscheidbarkeit oder Komplexitätsobergrenzen fließen entsprechend den Einschränkungen der Reduktion von der Ziel- zur Quelldomäne.

Umkehrung

Die Umkehrung, falls sie existiert, ist eine Reduktion in die entgegengesetzte Richtung; das Fehlen einer Rückreduktion weist auf eine Asymmetrie in Schwierigkeit oder Ausdrucksfähigkeit hin.

Abgrenzung

Reduktionen erfordern eine präzise Festlegung der erlaubten Ressourcen und Transformationen (Typ: many-one, Turing, polynomiell, parsimonisch usw.); Abbildungen, die das Akzeptanzkriterium ändern oder auf nichtkonstruktiven Schritten beruhen, fallen außerhalb des Umfangs.

Semantische Spannung

Reduktion vs. Äquivalenz: Eine Reduktion zeigt relative Transformierbarkeit, nicht notwendigerweise zweiseitige Äquivalenz; Reduktionen werden oft fälschlich mit Isomorphismen oder gegenseitigen Codierungen gleichgesetzt, wenn keine Bidirektionalität bewiesen ist.

Synthese

Reduktion ist eine konstruktive Brücke: eine berechenbare oder konstruktive Abbildung zusammen mit einer gültigen Rückübersetzung, die Lösbarkeit oder strukturelle Eigenschaften unter spezifizierten Ressourcenbeschränkungen von einer Domäne in eine andere verlagert.