On some promise classes in structural complexity theory

Rothe, Jörg GND

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 Gegenbeispiele 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.

Vorschau

Zitieren

Zitierform:

Rothe, Jörg: On some promise classes in structural complexity theory. 1995.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Export