Direkt zum Inhalt

Lexikon der Mathematik: Turing-Reduktion

Begriff im Kontext Komplexitätstheorie.

Ein Problem P1 ist auf ein Problem Turing- reduzierbar, Notation P1T P2, wenn es einen polynomialen Algorithmus gibt, der P1 löst und dabei in konstanter Zeit aus einer Black Box Lösungen für das Problem P2 erhält.

Ist P2 in polynomieller Zeit lösbar, ergibt sich ein polynomialer Algorithmus für P1, indem die Black Box durch den Algorithmus für P2 ersetzt wird. Turing-Reduktionen sind Verallgemeinerungen von polynomiellen Zeitreduktionen und nicht nur auf Sprachen und Entscheidungsprobleme, sondern auch auf Suchprobleme anwendbar.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos