NP-completeness notions under strong hypotheses

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.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Heidelberg

Year

2000

Author dc:creator

• Bentzien, Levke

Contributors dc:contributor

• Ambos-Spies, Klaus

Repository record source_url

http://www.ub.uni-heidelberg.de/archiv/1384

OAI identifier oai:identifier

oai:archiv.ub.uni-heidelberg.de:1384