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: |
| |||||||
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: | 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 |