Completeness for parallel access to NP and counting class separation

Abstract

Die Dissertation beschäftigt sich mit Problemen, die vollständig für die Komplexitätsklasse PNP sind, sowie mit der Separation von Zählklassen. PNP ist die Klasse der Probleme, die sich effizient mit parallelem Zugriff auf NP lösen lassen. Wir untersuchen die Komplexität von mit Wahlsystemen assoziierten Problemen. Wahlsysteme sind Vorschriften, nach denen aus einer Kandidatenmenge die Gewinner einer Abstimmung bestimmt werden können. Wir beweisen, daß das Gewinner- Problem für die Wahlsysteme von Kemeny und Young beide vollständig für die Klasse PNP sind. Weiterhin betrachten wir zwei prominente Heuristiken für die Approximation des NP-vollständigen Problems der minimalen Knotenüberdeckung. Wir weisen nach, daß gewisse Entscheidungsprobleme, die mit der Qualität der Approximation durch diese Heuristiken in Zusammenhang stehen, vollständig für PNP sind. Der letzte Teil der Dissertation beantwortet Fragen, die in der einflußreichen Arbeit von Fenner, Fortnow und Kurtz im Jahre 1994 aufgeworfen wurden: Wir zeigen, daß die Zählklassen LWPP und WPP nicht uniform gap-definierbar sind. Desweiteren konstruieren wir ein Orakel, relativ zu dem WPP nicht abgeschlossen unter polynomialzeitbeschränkter Turing-Reduzierbarkeit ist. Dies hat zur Folge, daß ein Beweis für die Gleichheit der ähnlich definierten Klassen LWPP und WPP nichtrelativierbar sein muß. Wir erhalten diese Resultate durch Anwendung einer bekannten Technik, bei der Orakel-Turingmaschinen in multilineare Polynome mit kleinem Grad kodiert werden. Wir beweisen dazu eine neue kombinatorische Eigenschaft solcher Polynome.