Ein Algorithmus ist eine endlich beschriebene, eindeutige Vorschrift aus ausführbaren Einzelschritten, die für jede Eingabe nach endlich vielen Schritten ein Ergebnis liefert. „Ausführbar“ ist dabei noch ungenau. Zur Präzisierung nutzt man ein einfaches Rechenmodell, die Turingmaschine (Alan Turing, 1936). Sie hat eine endliche Steuerung mit Zuständen, ein beidseitig unbegrenztes Band aus Feldern, die je ein Zeichen oder das Leerzeichen □ tragen, und einen Schreib-Lese-Kopf. In jedem Schritt hängt alles vom Zustand und dem Zeichen unter dem Kopf ab: Die Maschine schreibt ein Zeichen, bewegt den Kopf nach links (L), nach rechts (R) oder gar nicht (N) und wechselt den Zustand. Sie hält, wenn sie den Endzustand „halt“ erreicht.

Die Registermaschine aus der Rechnerarchitektur (Register mit Zahlen, Befehle zum Laden, Rechnen und Springen) ist ein zweites Modell. Man kann zeigen: Jede Registermaschine lässt sich durch eine Turingmaschine nachbilden und umgekehrt. Beide berechnen dieselben Funktionen.

Die Church-Turing-These (Alonzo Church, Alan Turing) besagt: Jede im anschaulichen Sinn berechenbare Funktion lässt sich von einer Turingmaschine berechnen. Sie ist eine These und kein Satz, denn „anschaulich berechenbar“ ist kein mathematischer Begriff, man kann sie nicht beweisen. Für sie spricht, dass alle vorgeschlagenen Modelle (Registermaschine, Programmiersprachen mit unbegrenztem Speicher und weitere) dieselben Funktionen berechnen und kein Gegenbeispiel bekannt ist.

Ein Entscheidungsproblem hat als Antwort ja oder nein, zum Beispiel: Ist n eine Primzahl? Es ist entscheidbar, wenn es einen Algorithmus gibt, der für jede Eingabe nach endlich vielen Schritten die richtige Antwort liefert. Sonst ist es unentscheidbar. Das Halteproblem fragt: Hält das Programm P bei der Eingabe x nach endlich vielen Schritten an?

Der Laufzeitaufwand zählt die Schritte eines Algorithmus in Abhängigkeit von der Eingabegröße n (O-Notation). Er heißt polynomiell, wenn er höchstens $n^k$ für ein festes k wächst, und exponentiell, wenn er wie $2^n$ wächst. Die Tabelle zeigt die Schrittzahl, dazu die Dauer bei angenommenen $10^9$ Schritten pro Sekunde:

Ein tausendmal schnellerer Rechner hilft bei $2^n$ kaum: Er schafft nur etwa 10 weitere Elemente, denn $2^{10} = 1024$.

P ist die Klasse der Entscheidungsprobleme, die ein Algorithmus in polynomieller Zeit löst. NP ist die Klasse der Entscheidungsprobleme, bei denen sich eine vorgeschlagene Lösung in polynomieller Zeit überprüfen lässt. Es gilt $\mathrm{P} \subseteq \mathrm{NP}$. Ob $\mathrm{P} = \mathrm{NP}$ gilt, ist ungeklärt. Die NP-vollständigen Probleme sind die schwersten in NP: Hätte eines einen polynomiellen Algorithmus, hätten ihn alle in NP. Keiner ist bekannt, vermutet wird $\mathrm{P} \ne \mathrm{NP}$.

• SAT: Gibt es für eine aussagenlogische Formel eine Belegung der Variablen, die sie wahr macht? Die Formel $(a \lor b) \land (\lnot a \lor c) \land (\lnot b \lor \lnot c)$ wird mit a = wahr, b = falsch, c = wahr wahr. Eine Belegung zu prüfen ist schnell, es gibt aber $2^n$ Belegungen. SAT ist NP-vollständig.
• Handlungsreisender: Gesucht ist die kürzeste Rundreise durch n Städte, die jede genau einmal besucht und zum Start zurückkehrt. Bei gleichen Wegen in beiden Richtungen gibt es $\frac{(n-1)!}{2}$ Rundreisen, bei 10 Städten 181440.
• Rucksackproblem: Gegenstände haben Gewicht und Wert, der Rucksack hat eine Tragfähigkeit. Gesucht ist die Auswahl mit dem höchsten Wert. Bei n Gegenständen gibt es $2^n$ Auswahlen.

Auch die Entscheidungsfassungen der beiden letzten Probleme sind NP-vollständig: „Gibt es eine Rundreise höchstens dieser Länge?“ und „Gibt es eine Auswahl mindestens dieses Wertes?“.

Brute-Force probiert alle Möglichkeiten durch. Das Ergebnis ist optimal, der Aufwand bei den Problemen oben aber exponentiell. Ein Greedy-Verfahren baut die Lösung Schritt für Schritt auf und nimmt jeweils, was im Moment am besten aussieht, ohne es zurückzunehmen. Es ist schnell, liefert aber nicht immer das Optimum. (Bei den kürzesten Wegen nach Dijkstra und den Spannbäumen nach Prim liefert es dagegen das Optimum.) Eine Näherungslösung ist eine Lösung, die nicht unbedingt optimal ist, aber in vertretbarer Zeit gefunden wird. Beim Handlungsreisenden geht man etwa stets zur nächsten noch nicht besuchten Stadt.