Algorithmen und Komplexitätstheorie
Ein Algorithmus kann in einer bestimmten Laufzeit eine Instanz eines Problems mit einer bestimmten Kodierungslänge (Größe der Instanz) lösen. Zur Angabe der Laufzeit kann man das O Kalkül verwenden.
Man kann Entscheidungsprobleme in verschiedene Komplexitätsklassen einteilen.
Man kann auch ein Optimierungsproblem in ein Entscheidungsproblem transformieren.