Turing Reducibility

Wie vergleicht man die Schwierigkeit von Problemen? "Ist A schwerer als B?" Idee: Ich gebe dir eine Zauberbox (Oracle), die B sofort löst. Kannst du mit dieser Box A lösen? Wenn Ja: "A ist auf B reduzierbar" ($A \leq_T B$). Dann ist A nicht schwerer als B. (Denn mit B als Hilfe ist A einfach). Beispiel: A = Multiplizieren. B = Addieren. Kann ich mit einer Addier-Box multiplizieren? Ja (durch wiederholtes Addieren). Also ist Multiplizieren nicht fundamental "mächtiger" als Addieren (im Sinne der Berechenbarkeit).

Merksatz: Eine Relation zwischen zwei Problemen A und B, die besagt, dass A gelöst werden kann, wenn man ein Orakel für B zur Verfügung hat (A ist algorithmisch auf B reduzierbar).

In der Komplexitätstheorie. Um zu zeigen, dass SAT NP-Complete ist. Man zeigt: Jedes Problem in NP kann auf SAT reduziert werden. Wenn wir SAT lösen können (Oracle), ist alles gelöst. Deshalb ist SAT "das schwerste" Problem.

1. Many-One vs. Turing Reduction

Many-One (Karp): Du darfst den Input nur einmal umwandeln und das Oracle fragen. $f(x) \in B \iff x \in A$. (Strenger).
Turing (Cook): Du darfst das Oracle beliebig oft fragen, loopen, das Ergebnis invertieren. (Flexibler). Halteproblem $H$ ist Turing-reduzierbar auf $\overline{H}$ (Komplement), aber nicht Many-One reduzierbar.

2. Degrees of Unsolvability

Man kann unlösbare Probleme klassifizieren. Ist das Halteproblem schwerer als das Problem "Ist die Turing Maschine leer"? Man baut eine Hierarchie der Unendlichkeit (Turing Degrees).

1. Arithmetic Hierarchy

Man kann Probleme in Schichten einteilen: $\Sigma_n, \Pi_n, \Delta_n$.

$\Sigma_1$: Probleme, die man "bestätigen" kann (Semi-entscheidbar wie das Halteproblem).
$\Sigma_2$: "Gibt es einen Input, für den das Programm unendlich läuft?" (Hier braucht man bereits ein Oracle für das Halteproblem). Turing Reducibility erlaubt es uns, die gesamte Mathematik des Berechenbaren in diese Stufen zu sortieren. Jede Stufe ist fundamental "magischer" als die darunter liegende.

2. Posts Problem & Friedberg-Muchnik

Gibt es Probleme zwischen "Einfach" (P/Decidable) und "Halteproblem" (Universal)? Emil Post fragte das 1944. Die Antwort (1956): Ja. Es gibt Probleme, die unentscheidbar sind, aber das Halteproblem nicht lösen können. Sie liegen in der "Mitte". Das zeigt, dass die Welt der Unlösbarkeit keine flache Wüste ist, sondern ein Gebirge mit unendlich vielen Gipfeln (Turing Degrees). In der theoretischen Forschung nutzt man die Priority Method, um solche Monster-Probleme zu konstruieren.

3. Relativierung von P vs NP

Kann man P vs NP durch Reduktion lösen? Baker, Gill und Solovay zeigten: Es gibt ein Oracle $A$, mit dem $P^A = NP^A$, und ein Oracle $B$, mit dem $P^B \neq NP^B$. Das bedeutet, dass jede Beweis-Technik, die gegenüber Oracles "blind" ist (und das sind fast alle, die wir haben), niemals P vs NP lösen kann. Wir müssen in die "Innereien" der Turing-Maschine schauen, anstatt sie nur als Blackbox zu betrachten. Dies ist einer der tiefsten Gründe, warum das Problem seit 50 Jahren ungelöst ist.