Vertragstheorie Eine Einführung mit finanzökonomischen Beispielen und Anwendungen 2005, XVI, 218 S. Basler, Herbert Grundbegriffe der Wahrscheinlichkeitsrechnung und Statistischen Methodenlehre

Abb. 2.1. Beispielgraph

Steiner-Problem in Graphen. Zielsetzung ist die Bestimmung eines Teilgra-

phen mit minimaler Gesamtstrecke derart, dass alle Knotenpaare aus einer

ausgezeichneten Teilmenge der Knoten des Graphen miteinander verbunden

sind.

F¨

ur das im Folgenden beschriebene Investitionsauswahlproblem sind eben-

falls keine effizienten Algorithmen bekannt. In der Unternehmenspraxis stellt

sich oft das Problem der effizienten Auswahl unter einer Menge von poten-

ziell durchf¨

uhrbaren Investitionsvorhaben, zwischen denen gewisse Zusam-

menh¨

ange bestehen. Beispielsweise k¨

onnen sich zwei Investitionsvorhaben ge-

genseitig ausschließen, gegenseitig bedingen oder wechselseitige, nicht exakt

quantifizierbare Kosten- oder Erfolgsauswirkungen besitzen. Folgende einfa-

che Abstraktion aus diesem Bereich ist wohlbekannt: Jedes Investitionsvorha-

ben i, 1 ≤ i ≤ n, besitzt einen bestimmten Kapitalwert e

i

und verursacht eine

Reihe von Nettoauszahlungen a

it

, die in Periode t, 1 ≤ t ≤ T , anfallen, wenn

die jeweilige Investition durchgef¨

uhrt wird. F¨

ur jede Periode t ist dabei ein

maximales Budget b

t

vorgegeben, welches nicht ¨

uberschritten werden darf.

Das Problem besteht darin, unter Einhaltung der Budgetrestriktionen in al-

len Perioden eine Auswahl der durchzuf¨

uhrenden Investitionen so zu treffen,

dass der Gesamtkapitalwert maximiert wird.

Es gibt eine große Anzahl von Problemstellungen, die ¨

ahnlich wie das

Rundreiseproblem, das Steiner-Problem in Graphen und das Investitionsaus-

wahlproblem folgende Eigenschaft besitzen: Man kann effizient eine L¨

osung

raten (nichtdeterministisch erzeugen) und ¨

uberpr¨

ufen, ob der Zielfunktions-

wert kleiner als eine vorgegebene Schranke ist. Die entsprechende Problem-

klasse f¨

ur solche Entscheidungsprobleme wird mit

N P bezeichnet.

9

N P stellt

trivialerweise eine Obermenge von

P dar.

10

Es gibt eine Vielzahl an relevan-

ten Problemen, die in

N P enthalten sind, f¨ur die man aber bisher keinen

effizienten Algorithmus kennt, sondern nur solche mit exponentiellem Auf-

9

N P steht f¨ur nichtdeterministisch polynomial und ist als die Klasse aller Proble-

me definiert, die auf einer nichtdeterministischen Turing-Maschine in polynomial

beschr¨

ankter Laufzeit berechnet werden k¨

onnen.

10

Hierbei vernachl¨

assigen wir die eigentlich erforderliche Unterscheidung in

Optimierungs- und Entscheidungsprobleme.

---

22

2. Informatik und Informations- und Kommunikationstechnik

wand. Diese

”

schweren“ Probleme in

N P werden als N P-schwer oder auch

als nicht handhabbar (intractable) bezeichnet (mit einigen Ausnahmen). In-

teressanterweise sind alle

N P-schweren Probleme in einem gewissen Sinne

”

gleich schwer“. Man kann zeigen, dass dann, wenn man auch nur f¨

ur eine

dieser Problemstellungen ein effizientes Verfahren angeben kann, auch die

¨

ubrigen effizient l¨

osbar sind. Bisher ist aber weder dies gelungen, noch konn-

te man nachweisen, dass zur L¨

osung

N P-schwerer Probleme keine effizienten

Algorithmen existieren. Die Frage

”P

=

N P?“ stellt das Hauptproblem der

Komplexit¨

atstheorie dar. Obwohl dieses Problem bisher nicht gel¨

ost werden

konnte, geht man aufgrund der umfangreichen (erfolglosen) Forschungsan-

strengungen im Hinblick auf effiziente Algorithmen f¨

ur

N P-schwere Probleme

davon aus, dass f¨

ur solche Probleme keine effizienten Algorithmen existieren.