On some promise classes in structural complexity theory / von Jörg Rothe

In dieser Dissertation werden sogenannte "promise classes" studiert, wie z.B. die wichtigen Komplexitätsklassen UP und FewP. Insbesondere wird untersucht, inwiefern sich bekannte Resultate für die gründlich untersuchte Klasse NP auf UP und FewP übertragen lassen. Hauptresultate: (1) Für die Äquivalenz von Booleschen Hierarchien ist der Abschluss unter Vereinigung (wie z.B. bei NP) nicht nötig: Die Boolesche Hierarchie alternierender Summen und die Symmetrische-Differenz-Hierarchie über einer nichttrivialen schnittabgeschlossenen Klasse (wie z.B. UP) stimmen mit der Booleschen Hülle der Klasse überein. Für die Differenz- und die Hausdorff-Hierarchie über UP werden relativierte Gegenspiele gegeben. (2) Hat UP Turing-schwere dünne Mengen, so ist UP in der zweiten Stufe der "low hierarchy" in NP; dieses Resultat wird auf die "promise unambiguous polynomial hierarchy" verallgemeinert. (3) Es wird gezeigt, dass FewP (wie NP) die Eigenschaft der "upward separation" besitzt. Dies widerlegt eine Vermutung von Allender. Dieses Resultat wird auch für andere Klassen erzielt wie die promise-Klassen SPP und LWPP. (4) Es wird ein Analagon der Klasse SPP definiert, das bezüglich randomisierter Reduktionen hart für die Polynomialzeit-Hierarchie ist. Dies beantwortet eine Frage von Toda und Ogihara teilweise. (5) Als Verallgemeinerung von Selmans P-selektiven Mengen werden die multi-selektiven Mengen eingeführt und die entsprechenden Hierarchien umfassend untersucht.

Saved in:
Person: Rothe, Jörg [Author]
Corporate Author: Friedrich-Schiller-Universität Jena [Degree granting institution]
Format: Book
Language(s):English
Publication:Jena, 1995
Printing place:Jena
Dissertation Note:Jena, Univ., Diss., 1995
Subjects:Strukturkomplexität > Komplexitätsklasse
Type of content:Hochschulschrift
Related resources:Erscheint auch als Online-Ausgabe: On some promise classes in structural complexity theory
Physical description:X, 112 S. : graph. Darst. ; 29 cm