Bentzien, Levke
German Title: NP-Vollständigkeitsbegriffe unter starken Annahmen
Preview |
PDF, English
Download (964kB) | Terms of use |
Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the DOI, URN or the persistent URL below, as we can guarantee their long-time accessibility.
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.
| Document type: | Dissertation |
|---|---|
| Supervisor: | Ambos-Spies, Prof. Dr. Klaus |
| Date of thesis defense: | 30 May 2000 |
| Date Deposited: | 20 Nov 2000 00:00 |
| Date: | 2000 |
| Faculties / Institutes: | The Faculty of Mathematics and Computer Science > Institut für Mathematik |
| DDC-classification: | 510 Mathematics |
| Controlled Keywords: | Komplexitätstheorie, Nichtdeterminismus, Vollständigkeit |
| Uncontrolled Keywords: | Generizität , ressourcenbeschränktcomplexity, nondeterminism , completeness , resource-bounded , genericity |
