In der Praxis der Informationstechnologie ist man immer wieder mit der Aufgabe konfrontiert, Software für die Lösung unterschiedlicher Aufgabenstellungen zu entwickeln. Hier eine kleine Auswahl an möglichen Problemstellungen:

1. Innerhalb eines Warenwirtschaftssystems sollen alle Bestellungen nach der Artikelnummer sortiert werden.
2. Für eine Spedition sollen Rundreisen mit einer minimalen Wegstrecke berechnet werden.
3. Eine IT-Abteilung will eine domänenspezifische Programmiersprache erstellen, die es dem Fachbereich erlaubt, auf einfache Weise Fachlogik zu implementieren.
4. Ein Hersteller von Entwicklungswerkzeugen will in seiner angebotenen Entwicklungsumgebung automatisch prüfen, ob ein gegebenes Programm auf einer gegebenen Eingabe terminiert.

Da Softwaresysteme in unserem Alltag mittlerweile allgegenwärtig sind, könnte man den Eindruck gewinnen, dass alle denkbaren Aufgabenstellungen durch entsprechende Algorithmen gelöst werden können. Dabei sind einige Aufgabenstellungen evtl. etwas schwieriger, wenn man aber lange genug forscht, sollte man aber auch für eine komplizierte Aufgabenstellung einen Algorithmus finden können.

Natürlich sollten die Algorithmen nicht zu lange für die Berechnung einer Ausgabe benötigen. Da wir jedoch sehen, wie dramatisch die Rechenleistung in den letzten Jahren angewachsen ist, sollten uns auch langsame Algorithmen keine Probleme bereiten. Wir können sie im Zweifel mit einer leistungsstärkeren Hardware beschleunigen.

Was wäre aber, wenn es doch Probleme gibt, für die kein Algorithmus existiert? Dann suchen wir über einen sehr langen Zeitraum mit erheblichen finanziellen Mitteln nach einer Lösung, die es gar nicht gibt. Wir würden sinnlos Ressourcen vergeuden.

Was wäre, wenn es Algorithmen gibt, die auch bei einer Vertausendfachung der Rechenleistung von aktuellen Großrechnern immer noch mehrere Jahrtausende für die Berechnung einer Ausgabe benötigen. Dann könnten wir die Aufgabenstellung praktisch nicht lösen. Wir müssten uns auf die Suche nach einem schnelleren Algorithmus machen.

Was wäre aber, wenn es überhaupt keinen schnelleren Algorithmus für die Aufgabenstellung gibt? Die Antwort sollte klar sein.

Betrachten wir noch einmal die vier oben aufgelisteten Problemstellungen. Für eines dieser Probleme gibt es effiziente (schnelle) Algorithmen. Für ein anderes Problem gibt es mit sehr hoher Wahrscheinlichkeit keinen effizienten Algorithmus. Für ein Problem gibt es überhaupt keinen Algorithmus. Für eine Problemstellung gibt es nur einen effizienten Algorithmus, wenn bestimmte Randbedingungen gelten.

Die Gefahr, dass wir bei der Entwicklung von Software sinnlos Ressourcen vergeuden, ist also real. Wir sind diesen Gefahren aber nicht völlig hilflos ausgeliefert. Zum Glück gibt es die Theoretische Informatik, die uns vor Fehlern schützen kann. Die Theoretische Informatik besitzt im Vergleich zu den anderen Gebieten der Informatik ein solides und breites wissenschaftliches Fundament. Während man häufig die kurze Halbwertszeit von Wissen in der Informationstechnologie beklagt, haben einige Aussagen der Theoretischen Informatik bereits seit über 40 Jahren ihre Relevanz bewahrt. Der Stoff dieser Vorlesung kann Sie also durchaus Ihr ganzes Berufsleben begleiten.