Redukce (teorie výpočetní složitosti)

Redukce  v teorii výpočetní složitosti  je transformace jednoho problému v jiný. Obecně platí, že pro algoritmus, který převádí instance problému na případy problému , které mají stejnou odpověď („ano“ nebo „ne“), se říká, že se redukuje na , takže redukovatelnost  je vztah mezi dvěma problémy. Pomocí takového spojení lze prokázat vyčíslitelnost problému nebo jeho příslušnost k té či oné třídě složitosti .

Některé typy informací: Cookeova redukce , Karp redukce , Levinova redukce , Turingova redukce . Turingova redukce je nejobecnější formou redukce: nějaký algoritmus (vypočitatelný na Turingově stroji ) může být volán libovolný počet časů a každé volání bude považováno za jeden krok algoritmu; k formální definici Turingovy redukovatelnosti se používá koncept Turingova stroje s věštcem .

Literatura

Odkazy