On the complexity of alternative solutions

Diese Dissertation untersucht die Komplexität alternativer Lösungen. Das heißt, wir betrachten die Frage, ob eine oder mehrere gegebene Lösungen eines Problems, das Finden weiterer Lösungen vereinfacht. In der Praxis relevant ist diese Fragestellung zum Beispiel, wenn sich eine mit großem Aufwand berechnete Lösung eines schwierigen Problems im Nachhinein als unzureichend erweist. In diesem Falle ist es notwendig nach alternativen Lösungen zu suchen, wobei nun die bereits gefundene Lösung als Ausgangspunkt der Berechnung genutzt werden kann. Darüber hinaus hat die untersuchte Aufgabenstellung eine Bedeutung in der Erstellung von (auch hier immer beliebteren) japanischen Rätseln wie Sudoku, Kakkuro oder Nurikabe. Beispielsweise werden im Fall von Sudoku, ausgehend von einem vollständig ausgefüllten Gitter (Startlösung), Ziffern so gestrichen dass die Startlösung die eindeutige Lösung des Rätsels bleibt. Dazu muss während des Streichprozesses wiederholt geprüft werden, ob es neben der Startlösung alternative Lösungen gibt. Im ersten Teil der Arbeit (Kapitel 3 und 4) betrachten wir die Klasse der NP-vollständigen Probleme. Wir formalisieren den Begriff der Lösung mittels sogenannter Verifier und das Problem alternativer Lösungen für NP-Sprachen. Indem wir die Härte des Problems alternativer Lösungen für einige Probleme zeigen, motivieren wir die Vermutung, dass eine gegebene Lösung das Finden alternativer Lösungen nicht vereinfacht. Wir entwickeln den Begriff des universellen Verifiers, der es ermöglicht, einen geeigneten Lösungsbegriff für ein Problem formal zu charakterisieren. Darüber hinaus zeigen wir, dass es möglich ist, mit einer einzigen sogenannten -Reduzierung einen Lösungsbegriff für ein Problem als geeignet zu identifizieren sowie die Härte des Problems alternativer Lösungen für jede Anzahl gegebener Lösungen zu zeigen. Unter Benutzung dieser Reduzierung, erhärten wir die obige Vermutung, indem wir für eine große Zahl NP-vollständiger Probleme wie zum Beispiel 0/1-Integer Programming, 3Dimensional Matching, Minimum Edge Cost Flow und Vertex Cover zeigen, dass bezüglich eines geeigneten Lösungsbegriffes alternative Lösungen nicht leicht zu berechnen sind. Darüber hinaus übertragen wir die Theorie für NP-Probleme auch auf die Klasse RE der aufzählbaren Sprachen (Kapitel 5) und die Klassen der Polynomialzeithierarchie (Kapitel 6). Für RE zeigen wir damit, dass das Problem alternativer Lösungen für RE wenig sinnvoll ist, da wir für jedes RE-Problem einen geeigneten Lösungsbegriff finden, der höchstens eine Lösung zulässt. Die Situation in der Polynomialzeithierarchie ist vermutlich ähnlich zum NP-Fall. Für können wir die Härte des Problems alternativer Lösungen für einige typische Probleme zeigen, z.B. für Generalized Subset Sum und Strongest Implicant Core. Deshalb und wegen der starken strukturellen Ähnlichkeit zu NP (Die Polynomialzeithierarchie ist eine Verallgemeinerung von NP, insbesondere gilt = NP) vermuten wir auch hier, dass alternative Lösungen im Allgemeinen genauso schwer zu finden sind, wie eine erste Lösung.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten