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)