Turingova redukce

Turingova redukce v teorii vyčíslitelnosti definuje: problém Π₁ je Turing-redukovatelný na Π₂ (Π₁ ∝ Π₂), jestliže existuje program pro (deterministický) Turingův stroj, který řeší každou instanci I₁ problému Π₁ tak, že používá program M₂ pro problém Π₂ jako podprogram (jehož trvání považujeme za jeden krok).

Zvláštním případem Turingovy redukce je Cookova redukce, která převod dokáže v polynomiálním čase.

Reference

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.