Dokument: Completeness for Parallel Access to NP and Counting Class Separations

Titel:Completeness for Parallel Access to NP and Counting Class Separations
URL für Lesezeichen:https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=3172
URN (NBN):urn:nbn:de:hbz:061-20050720-001172-8
Kollektion:Dissertationen
Sprache:Englisch
Dokumententyp:Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:Text
Autor: Spakowski, Holger [Autor]
Dateien:
[Dateien anzeigen]Adobe PDF
[Details]587,1 KB in einer Datei
[ZIP-Datei erzeugen]
Dateien vom 09.02.2007 / geändert 09.02.2007
Beitragende:Prof. Dr. Rothe, Jörg [Gutachter]
Prof. Dr. Wagner, Klaus W. [Gutachter]
Prof. Dr. Wanke, Egon [Gutachter]
Stichwörter:Orakelberechnung, Vollständigkeit, Wahlsysteme, Heuristiken, Zähklassen, Relativierung
Dewey Dezimal-Klassifikation:000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibung:Diese Arbeit beschäftigt sich mit Problemen, die vollständig für die
Komplexitätsklasse P^NP_{||} sind, sowie mit der Separation von Zählklassen.
P^NP_{||} ist die Klasse der Probleme, die sich effizient mit parallelem
Zugriff auf NP lösen lassen. Ausgangspunkt unserer Untersuchungen
ist eine Charakterisierung der Klasse P^NP_{||} durch nichtdeterministische Turingmaschinen mit einem speziellen Akzeptierungsmechanismus. Das Akzeptierungsverhalten solcher Turingmaschinen läßt sich durch boolesche Formeln beschreiben. Wir erhalten auf diese Weise P^NP_{||}-vollständige
Erfüllbarkeitsprobleme, in Analogie zu dem klassischen NP-vollständigen
Erfüllbarkeitsproblem 3SAT. Wie in der Theorie der NP-Vollständigkeit eignen
sich diese Probleme als Startpunkte für Reduktionen auf weitere Probleme. Wir
gelangen z.B. zu einem alternativen Beweis für das Resultat von Wagner, daß das Problem Minimum Vertex Cover Compare P^NP_{||}-vollständig ist.
Dieses Entscheidungsproblem nutzen wir in der Arbeit für den Nachweis der
P^NP_{||}-Vollständigkeit von weiteren Problemen.

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ß die Gewinner-Probleme für die Wahlsysteme von Kemeny und Young beide vollständig für die Klasse P^NP_{||} 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 P^NP_{||} sind.

Im letzten Teil der Dissertation beantworten wir 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.
Lizenz:In Copyright
Urheberrechtsschutz
Fachbereich / Einrichtung:Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik
Dokument erstellt am:20.07.2005
Dateien geändert am:12.02.2007
Promotionsantrag am:14.07.2005
Datum der Promotion:14.07.2005
english
Benutzer
Status: Gast
Aktionen