Jedes algorithmische Problem, das in irgendeiner Programmiersprache programmiert und auf irgendeinem dafür geeigneten Computer ausgeführt werden werden (sogar auf Computern, die noch nicht gebaut sind, aber prinzipiell gebaut werden könnten), und selbst wenn es unbeschränkt viel Zeit und Speicherplatz für immer grössere Eingaben benötigt - jedes solche Programm ist auch durch eine Turing-Maschine lösbar.

Als Eingabe wird das Halteproblem "gefüttert" mit dem Text eines zulässigen Programms A in unserer ausgewählten Programmiersprache Spr und einer möglichen Eingabe X (die nichts anderes als eine Folge von Symbolen ist). Das Problem fragt danach, ob A anhalten würde, wenn wir es mit der Eingabe X laufen liessen.

NP (ohne "-vollständig") steht für die Klasse der Probleme, für die es magische, nicht-deterministische Polynomialzeit-Algorithmen gibt.

Die NP-vollständigen Probleme sind die "härtesten" in NP, und zwar in dem "alle-mit-einem"-Sinn: Falls eines von ihnen in P liegen sollte, dann sind alle anderen Probleme aus NP auch in P.

PTIME oder manchmal kurz P steht für die Klasse der Probleme mit Polynomialzeit-Algorithmen, also derjenigen Probleme, die wir bislang gut oder durchführbar genannt haben.