20
2. Informatik und Informations- und Kommunikationstechnik
alle mit einer Laufzeitkomplexit¨
at von O(p
n
) f¨
ur ein konstantes
p bezeichnet
man als exponentiell. W¨
ahrend exponentielle Algorithmen auch mit schnel-
leren Rechnern f¨
ur große Probleme in der Regel nicht mehr brauchbar sind,
werden die polynomialen Verfahren zusammenfassend als effizient bezeichnet.
Bei den bisherigen Darlegungen stand die Komplexit¨
atsabsch¨
atzung f¨
ur
einen gegebenen Algorithmus
”
nach oben“ im Mittelpunkt. Eine interessan-
te Verallgemeinerung besteht darin, Komplexit¨
atsabsch¨
atzungen f¨
ur Proble-
me anstatt f¨
ur Algorithmen anzugeben. So besitzt der Standardalgorithmus
f¨
ur die Multiplikation zweier n × n Matrizen eine Komplexit¨at von O(n
3
).
W¨
ahrend die Frage, ob es auch schneller geht, durch Angabe und Unter-
suchung eines entsprechenden Algorithmus teilweise beantwortbar ist, erfor-
dert eine Komplexit¨
atsabsch¨
atzung
”
nach unten“ andere Techniken. Untere
Schranken werden als
Ω(
. . .) angegeben. Da eine Matrizenmultiplikation alle
n
2
Matrixelemente der Ergebnismatrix erzeugen muss, ergibt sich eine trivia-
le untere Schranke von
Ω(
n
2
). Eine Zielsetzung der Komplexit¨
atstheorie ist
es, die exakte Laufzeitkomplexit¨
at von Problemstellungen, die ¨
uber Θ(. . .)
ausgedr¨
uckt wird, zu bestimmen.
8
W¨
ahrend die Bestimmung der exakten Problemkomplexit¨
at im Bereich
der polynomialen Funktionen oft eher von theoretischem Interesse ist, ist
es f¨
ur viele Problemstellungen offen, ob sie ¨
uberhaupt effizient l¨
osbar sind
(d. h. mit einem Algorithmus mit polynomialer Laufzeit). Mit
P bezeichnet
man die Komplexit¨
atsklasse aller Probleme, die effizient l¨
osbar sind. Alle bis-
her angesprochenen konkreten Probleme (Sortieren, Matrizenmultiplikation
usw.) liegen in
P. Auch folgende Problemstellung ist effizient l¨osbar: Man
betrachte den in Abbildung 2.1 dargestellten Graphen, der ein Verkehrsnetz-
werk repr¨
asentiere. Die Knoten repr¨
asentieren Standorte, die eingezeichne-
ten Verbindungen stellen die existierenden Verkehrswege mit den entspre-
chenden Entfernungen dar. Das K¨
urzeste-Wege-Problem (vgl. u. a. Domschke
und Drexl (2005)) besteht darin, den k¨
urzesten Weg von einem gegebenen
Start- zu einem gegebenen Zielstandort zu bestimmen. Beispielsweise sei der
k¨
urzeste Weg vom Knoten 1 zum Knoten 8 gesucht. F¨
ur diese Problemstel-
lung existieren Verfahren mit einem Zeitaufwand von O(n
2
), wobei n die
Anzahl der Knoten bezeichnet.
Das Rundreiseproblem (Problem des Handlungsreisenden, Traveling-
Salesman-Problem)
ist relativ ¨
ahnlich zum K¨
urzeste-Wege-Problem: F¨
ur
einen gegebenen Graphen (der wie beim K¨
urzeste-Wege-Problem Standorten
und Verkehrsverbindungen mit ihren Entfernungen entspricht) ist eine Rund-
reise durch alle Standorte zu bestimmen, so dass die insgesamt zur¨
uckgelegte
Strecke (Gesamtstrecke) minimal ist. F¨
ur die optimale L¨
osung dieser Prob-
lemstellung sind jedoch nur exponentielle Algorithmen bekannt. Ein weiteres
solches Problem, f¨
ur das keine effizienten Algorithmen bekannt sind, ist das
8
Die exakte Laufzeitkomplexit¨
at der Matrizenmultiplikation ist unbekannt,
w¨
ahrend zumindest entsprechende Algorithmen mit einem Aufwand von
O(
n
2,376
) bekannt sind; vgl. Cormen et al. (2004).