TY  - GEN
Y1  - 2000///
TI  - NP-completeness notions under strong hypotheses
AV  - public
KW  - Generizität 
KW  -  ressourcenbeschränktcomplexity
KW  -  nondeterminism 
KW  -  completeness 
KW  -  resource-bounded 
KW  -  genericity
ID  - heidok1384
UR  - https://archiv.ub.uni-heidelberg.de/volltextserver/1384/
A1  - Bentzien, Levke
N2  - 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.
ER  -