Search

Die Dissertation kombiniert Durchschnittskomplexität (Average-Case Complexity) mit der Frage der Approximierbarkeit von Optimierungsproblemen. Beides sind Möglichkeiten mit dem Problem umzugehen, dass viele Berechnungsprobleme nicht mit polynomieller Laufzeitschranke berechenbar sind, es sei denn P = NP. Dafür wird ein theoretischer Rahmen vorgestellt, der sowohl die Klassifizierung von Optimierungsproblemen in Hinblick auf ihre Approximierbarkeit im Durchschnitt als auch die Untersuchung der strukturellen Eigenschaften der entstandenen Average-Case Approximationsklassen gestattet. Anstatt strikte obere Schranken für die Zeit anzugeben, die benötigt wird, um das Wortproblem für Entscheidungsprobleme zu lösen, betrachtet man in der Average-Case Komplexitätstheorie die durchschnittliche Zeit, die für diese Aufgabe benötigt wird. Die durchschnittliche Zeit wird bezüglich einer Wahrscheinlichkeitsverteilung auf den Eingabeinstanzen bestimmt, d.h. durchschnittliche Eigenschaften werden nie für ein Entscheidungsproblem allein angegeben, sondern für ein Entscheidungsproblem kombiniert mit einer Eingabeverteilung: ein randomisiertes Entscheidungsproblem. Bei der Untersuchung der durchschnittlichen Approximierbarkeit von randomisierten Optimierungsproblemen sind nicht nur Approximationsalgorithmen interessant, deren Laufzeit im Durchschnitt polynomiell ist. Bei der Suche nach Approximationsalgorithmen für ein Optimierungsproblem ist man an Algorithmen mit möglichst kleiner Performance Ratio interessiert. Um nun strikte obere Schranken für die Performance Ratio zu durchschnittlichen Schranken abzuschwächen, werden entsprechende Konzepte benötigt, die uns erlauben, Approximierbarkeit mit durchschnittlich konstantem, polynomiellem oder exponentiellem Faktor auszudrücken. Entsprechende Konzepte für durchschnittlich polynomielle und durchschnittlich exponentielle Funktionen sind bereits bekannt, der Begriff der durchschnittlich konstanten Funktionen wird in dieser Arbeit eingeführt. Eine Reihe von Ergebnissen über das durchschnittliche Verhalten von Approximationsalgorithmen für praktische Probleme dient der Illustration, wie sich diese Ergebnisse in das neue Rahmenwerk eingliedern. Mit Hilfe dieses definitorischen Rahmen untersuche ich die strukturellen Eigenschaften der Average-Case Approximationsklassen. Die Einführung einer die durchschnittliche Approximierbarkeit erhaltenden Reduktion ermöglicht es zu zeigen, dass die Klasse aller NP-Optimierungsprobleme mit P-berechenbaren Eingabeverteilungen vollständige Probleme besitzt. Unterschiede zwischen der Worst-Case Komplexität und der Average-Case Komplexität werden deutlich, wenn man die Average-Case Varianten der in der Worst-Case Komplexität betrachteten Relation "P = NP jedes NP-Problem lässt sich in polynomieller Zeit entscheiden" untersucht. Die Frage, ob NP im Durchschnitt leicht zu entscheiden ist ? das heißt, ob sich alle NP-Probleme mit P-berechenbaren Eingabeverteilungen in durchschnittlich polynomieller Zeit lösen lassen ? stellt sich als äquivalent heraus zur Frage, ob alle NP-Optimierungsproblem mit P-berechenbaren Eingabeverteilungen ein Approximationsschema mit durchschnittlich polynomieller Laufzeit besitzen. Die Durchschnittsapproximationsklassen, die durch im Schnitt polynomielle Laufzeit definiert sind, bilden eine strikte Hierarchie, falls NP nicht im Durchschnitt leicht zu entscheiden ist. Indem man die Existenz eines Approximationsalgorithmus', der eine Schranke für die Performance Ratio im Durchschnitt einhält, mit der Existenz eines (durchschnittlich) polynomiellen Algorithmenschemas für ein randomisiertes Entscheidungsproblem verknüpft, lassen sich entsprechende Hierarchieresultate auch für die Average-Case Approximationsklassen, die durch im Durchschnitt einzuhaltende Schranken für die Performance Ratio definiert sind, erzielen. Ein Algorithmenschema ist dabei ein Algorithmus, der Fehler machen darf; die Fehlerwahrscheinlichkeit hängt von der Eingabeverteilung ab und wird durch einen zusätzlichen Eingabeparameter beschränkt, der polynomiell in die Laufzeitschranke des Algorithmenschemas einfließt. Die Hierarchieergebnisse werden unter der Annahme erzielt, dass nicht alle NP-Probleme mit P-berechenbaren Eingabeverteilungen (durchschnittlich) polynomielle Algorithmenschemata besitzen. This thesis combines average-case complexity theory with the approximability of optimisation problems. Both are ways of dealing with the fact that many computational problems are not solvable in polynomial time, unless P = NP. A theoretical framework is established that allows both the classification of optimisation problems with respect to their average-case approximability and the study of the structural properties of the resulting average-case approximation classes. Instead of giving worst-case bounds on the time required to decide membership for a decision problem, average-case complexity focuses on the average time that is needed for this task. The average time is taken with respect to a probability distribution on the instances, so average-case properties are not given for a decision problem alone but for a decision problem combined with an input distribution: a distributional problem. For distributional optimisation problems, not only approximation algorithms that run in average polynomial time rather than worst-case polynomial time are of interest. When searching for approximation algorithms for an optimisation problem one aims for algorithms with small performance ratio. In order to relax the worst-case requirements on the performance ratio to average-case requirements, notions are needed to express approximability within a factor that is constant, polynomial or exponential on average. While respective concepts exist for the latter two, the notion of functions that are constant on average is introduced in this thesis. For a number of results on the average behaviour of approximation algorithms for practical problems it is shown how they fit into the new framework. With the framework of definitions established, we can examine the structural properties of the average-case approximation classes. Introducing a reduction that preserves average-case approximability, it is shown that the class of NP-optimisation problems with P-computable input distributions has complete problems. Differences between the worst-case and the average-case setting become apparent when looking at the average-case variant of the worst-case relation "P = NP every NP-optimisation problem is solvable in polynomial time". The question whether NP is easy on average ? which means that all NP-problems with P-computable input distributions are solvable in average polynomial time ? turns out to be equivalent to the question whether every NP-optimisation problem with a P-computable input distribution has an average polynomial time approximation scheme. The average polynomial time approximation classes form a strict hierarchy if NP is not easy on average. By linking the existence of average-ratio approximation algorithms for distributional optimisation problems to the existence of (average-) polynomial-time algorithm schemes for distributional decision problems, similar hierarchy results can be obtained for the average-ratio classes. An algorithm scheme is an algorithm that is allowed to make errors for some inputs; the error probability depends on the input distribution and is bounded by an additional input parameter that has a polynomial influence on the running time. The hierarchy results are shown under the premise that not all NP-problems with P-computable input distributions have (average-) polynomial-time algorithm schemes.