Theoretische Informatik

In der theoretischen Informatik kann man Probleme in Komplexitätsklassen aufteilen. Da man in der Vorlesung nur P, NP, NP-hart und NP-vollständig kennen lernt, beschränke ich diesen Beitrag auch auf diese Klassen. Hier findet man eine Übersicht über die weiteren Klassen Link. Für den Anfang reichen diese jedoch 😉

Das Halteproblem beschreibt ein Thema aus der theoretischen Informatik. Es geht dabei um die Frage, ob es einen Algorithmus gibt, der für einen beliebigen Algorithmus mit einer beliebigen Eingabe, entscheidet, ob er zu einem Ende kommt, oder nicht. Anders ausgedrückt: Gibt es ein Programm, das als Eingabe ein anderes Programm + Eingabe erhält und als Ausgabe