Bentzien, Levke
Deutsche Übersetzung des Titels: NP-Vollständigkeitsbegriffe unter starken Annahmen
Vorschau |
PDF, Englisch
Download (964kB) | Nutzungsbedingungen |
Zitieren von Dokumenten: Bitte verwenden Sie für Zitate nicht die URL in der Adresszeile Ihres Webbrowsers, sondern entweder die angegebene DOI, URN oder die persistente URL, deren langfristige Verfügbarkeit wir garantieren.
[mehr ...]
Abstract
A variety of completeness notions for the complexity class NP are studied under strong hypotheses about the size of this class. These hypotheses are based on the concept of resource-bounded genericity developed by Ambos-Spies, Fleischhack and Huwig. It is shown that many natural completeness notions for NP can be separated under such hypotheses. E.g., Turing- and truth-table-completeness, truth-table- and bounded-truth-table-completeness (btt-completeness), btt-completeness with two allowed queries and btt-completeness with three allowed queries, and others.
| Dokumententyp: | Dissertation |
|---|---|
| Erstgutachter: | Ambos-Spies, Prof. Dr. Klaus |
| Tag der Prüfung: | 30 Mai 2000 |
| Erstellungsdatum: | 20 Nov. 2000 00:00 |
| Erscheinungsjahr: | 2000 |
| Institute/Einrichtungen: | Fakultät für Mathematik und Informatik > Institut für Mathematik |
| DDC-Sachgruppe: | 510 Mathematik |
| Normierte Schlagwörter: | Komplexitätstheorie, Nichtdeterminismus, Vollständigkeit |
| Freie Schlagwörter: | Generizität , ressourcenbeschränktcomplexity, nondeterminism , completeness , resource-bounded , genericity |
