Reduktion SAT #50
Description
Im Foliensatz zur 9. Vorlesung, Folie 18 heißt es "Durch direkte Reduktion auf das Wortproblem von polynomiell zeitbeschränkten NTMs".
Ist es nicht genau anders herum, dass wir das Wortproblem auf SAT reduzieren wollen?
{{ message }}