Motivation

Wenn man ein (Graphen-)Problem durch einen effizienten Algorithmus lösen kann, dann ist alles gut. Wenn man aber trotz größter Mühe keinen effizienten Algorithmus findet, dann möchte man doch wissen, warum.

Dazu braucht man eine sinnvolle Definition für den Begriff ,,schwieriges Problem`` sowie zum Vergleichen der Schwierigkeit von Problemen.

Wenn man dann zeigen kann, daß ein Problem in diesem Sinne schwer ist, hat die Suche nach einem effizienten Algorithmus keinen Zweck.

Man kann stattdessen suchen nach effizienten Algorithmen für

• Näherungslösungen,
• exakte Lösungen für gewisse Teilmengen der möglichen Eingaben.