Auch für NP-harte Probleme gibt es effiziente Algorithmen, die das fragliche Problem in einem geeigneten Sinne approximieren können.

Nach Einführung einiger exemplarischer Approximationsalgorithmen wendet sich die Vorlesung dem Problem zu, Schranken, bzw. Grenzen an die effiziente Approximierbarkeit von NP-harten Problemen nachzuweisen. Diese teilweise erstaunlich guten Schranken basieren auf überraschenden Zusammenhängen mit der Theorie "interaktiver Beweissysteme" und der damit zusammenhängenden "zero knowledge" Theorie. Diese Zusammenhänge sind auch in der Kryptologie von Interesse. Dieses Thema wird allgemein als eines der interessantesten und überraschendsten der neueren Theoretischen Informatik angesehen.

Die relevanten Techniken werden in der Vorlesung im einzelnen dargeboten. Von allgemeinerem Erkenntniswert sind darüberhinaus die notwendigen und detailliert dargebotenen Techniken der (diskreten) Wahrscheinlichkeitslehre.