Begriff im Kontext Komplexitätstheorie.

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

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