Link zum Thema Reduktion (Theoretische Informatik)
Von: , Frage gestellt am So, 24. Aug 2008
Wo gibt es eine etwas leichtere Erklärung zur Reduktion verschiedener Entscheidungsprobleme?
Ich finde die meisten Eklärungen zu diesem Thema ziemlich umständlich und verkompliziert. Gibt es nicht einen einzigen Artikel, der ein paar Reduktionen beispielhaft durchführt.
Beispielsweise
SAT reduziert auf 3-SAT
HAMILTON reduziert auf SAT
HAMILTON reduziert auf Travelling salesman problem(TSP)
(Theoretische Informatik)