Turing- und Many-One-Reduktionen: Schlüsselkonzepte zur Problemlösung in der Informatik

Probleme lassen sich lösen, indem man sie auf bereits gelöste Probleme reduziert. Das gilt auch in der Informatik. Allerdings gibt es mehrere Arten ein Problem auf ein anderes zu reduzieren. Die Turing-Reduktion ist dabei die allgemeinste: Wir nutzen die bekannte Problemlösung wie eine Subroutine in einem Programm um letztlich zur Gesamtlösung zu kommen. Die Many-One-Reduktion reduziert dagegen die ursprüngliche Fragestellung auf eine andere, die dann nur noch (ein einziges Mal) gelöst werden muss um die Antwort zu erfahren.

► Playliste für diesen Videokurs: https://www.youtube.com/playlist?list=PLz7XhF-sAU8z4FtL7V9uefCXzW9Z9rk5c
► Vorlesungsfolien zum Download: https://iccl.inf.tu-dresden.de/web/TheoLog2021 (4. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: https://iccl.inf.tu-dresden.de/web/TheoLog
► Fehler gefunden? Issues melden auf github: https://github.com/knowsys/TheoLog