German Title: NP-Vollständigkeitsbegriffe unter starken Annahmen
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.
|Supervisor:||Ambos-Spies, Prof. Dr. Klaus|
|Date of thesis defense:||30 May 2000|
|Faculties / Institutes:||The Faculty of Mathematics and Computer Science > Department of Mathematics|
|Controlled Keywords:||Komplexitätstheorie, Nichtdeterminismus, Vollständigkeit|
|Uncontrolled Keywords:||Generizität , ressourcenbeschränktcomplexity, nondeterminism , completeness , resource-bounded , genericity|