Lexikon der Mathematik: Turing-Reduktion
Begriff im Kontext Komplexitätstheorie.
Ein Problem P1 ist auf ein Problem Turing- reduzierbar, Notation P1 ≤TP2, 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.
Copyright Springer Verlag GmbH Deutschland 2017
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.