Karpova redukce

Z Wikipedie, otevřené encyklopedie

Definice Karpovy redukce: Řekneme, že jazyk B je karpovsky redukovatelný na jazyk A, píšeme B ≤P A, pokud existuje deterministický Turingův stroj R takový, že R(x) ∈ A, právě když x ∈ B. Tedy, pokud stroj převede každou instanci problému B na instanci problému A tak, že výstup instancí je shodný.[1]

Reference[editovat | editovat zdroj]

  1. HOLUB, Štěpán. Algoritmy a problémy [online]. [cit. 2022-11-17]. Dostupné online.