KursbeschreibungAnschließend an den Kurs 01657 widmet sich der Kurs 01658 den nicht-berechenbaren Problemen. Hier werden wichtige Probleme, wie das Halteproblem, vorgestellt und wichtige Konsequenzen (Satz von Rice) erläutert. Des Weiteren wird eine Einführung in die Komplexitätstheorie gegeben. In diesem Zusammenhang werden die Komplexitätsmaße Zeit und Speicherplatz, untere und obere Schranken für die Komplexität von Problemen und Komplexitätsklassen eingeführt. Mit einer eingehenden Behandlung des P-vs-NP-Problems und der NP-Vollständigkeitstheorie schließt dieser Teil.