NP-completeness notions under strong hypotheses
type: CreativeWork
description: 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.
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.
author: Bentzien, Levke
date published: 2000-05-30
date modified: 2026-07-24T02:28:55Z
provider: Universität Heidelberg
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Universität Heidelberg