Reduzierbarkeit und Grade der Unlösbarkeit

Reduzierbarkeit vergleicht die Schwierigkeit von Problemen, indem sie eines in ein anderes umwandelt, und die Gruppierung von Problemen gleicher Schwierigkeit erzeugt die Grade der Unlösbarkeit, die die Welt jenseits des Berechenbaren strukturieren.

Definition

Ein Problem reduziert sich auf ein anderes, wenn ein Algorithmus, der Zugriff auf einen Löser für das zweite hat, das erste lösen kann; Probleme, die sich aufeinander reduzieren, teilen einen Grad der Unlösbarkeit, und diese Grade bilden eine Ordnung, die die relative algorithmische Schwierigkeit misst.

Scope

Dieses Thema behandelt die Many-One- und Turing-Reduzierbarkeit, die Verwendung von Reduktionen zum Beweis der Unentscheidbarkeit, die Turing-Sprungoperation, die streng schwierigere Probleme erzeugt, die arithmetische Hierarchie, die Probleme nach logischer Komplexität klassifiziert, und zentrale Ergebnisse der Gradtheorie wie die Existenz von Zwischengraden.

Core questions

• Wie können wir sagen, dass ein unlösbares Problem schwieriger ist als ein anderes?
• Wie werden Reduktionen sowohl zum Beweis der Unentscheidbarkeit als auch zur Organisation von Problemen verwendet?
• Was erzeugt der Turing-Sprung, und warum ist er immer streng schwieriger?
• Gibt es Probleme, die streng zwischen dem Entscheidbaren und dem Halteproblem liegen?

Key theories

Reduzierbarkeit und der Turing-Sprung

Die Turing-Reduzierbarkeit verbindet Probleme durch Orakelberechnung, und der Sprung eines Problems, der das Halten relativ dazu kodiert, ist immer streng schwieriger, wodurch ein unendlicher Turm immer schwierigerer Probleme entsteht.

Existenz von Zwischengraden

Das Friedberg-Muchnik-Theorem löste Posts Problem, indem es rekursiv aufzählbare Probleme konstruierte, die unentscheidbar, aber streng einfacher als das Halteproblem sind, unter Verwendung der Prioritätsmethode, was zeigt, dass die Grade eine reiche Struktur aufweisen.

Clinical relevance

Die Reduktionstechnik ist das alltägliche Werkzeug zum Nachweis der Unlösbarkeit von Problemen oder, in der Komplexitätstheorie, der Unlösbarkeit: Der Nachweis, dass ein bekanntes schwieriges Problem auf ein neues reduziert wird, überträgt die Schwierigkeit, was genau die Art und Weise ist, wie Unentscheidbarkeits- und NP-Vollständigkeitsergebnisse in Mathematik und Informatik etabliert werden.

History

Turing führte 1939 Orakelmaschinen ein, und Post formulierte 1944 die Untersuchung der Grade der Unlösbarkeit und stellte das Problem, ob Zwischengrade von rekursiv aufzählbaren Mengen existieren. Friedberg und Muchnik lösten es 1956–1957 unabhängig voneinander durch die Erfindung der Prioritätsmethode, die zu einer zentralen Technik des Fachgebiets wurde.

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

Was ist eine Reduktion, intuitiv?

Es ist eine Methode, ein Problem mithilfe eines Lösers für ein anderes zu lösen. Wenn man jede Instanz von Problem A in eine Instanz von Problem B übersetzen kann, sodass die Antworten übereinstimmen, dann ist B mindestens so schwer wie A, und eine Lösung für B liefert eine Lösung für A.

Gibt es Probleme, die schwieriger sind als das Halteproblem?

Ja, unendlich viele. Die Anwendung des Turing-Sprungs auf das Halteproblem ergibt ein streng schwierigeres Problem, und die Wiederholung der Operation baut eine endlose Hierarchie auf, sodass Unlösbarkeit in unbegrenzten Graden und nicht auf einer einzigen Ebene auftritt.