title: NP-completeness notions under strong hypotheses
creator: Bentzien, Levke
subject: ddc-510
subject: 510 Mathematics
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.
date: 2000
type: Dissertation
type: info:eu-repo/semantics/doctoralThesis
type: NonPeerReviewed
format: application/pdf
identifier: https://archiv.ub.uni-heidelberg.de/volltextserverhttps://archiv.ub.uni-heidelberg.de/volltextserver/1384/1/NPCompleteness.pdf
identifier: DOI:10.11588/heidok.00001384
identifier: urn:nbn:de:bsz:16-opus-13840
identifier:   Bentzien, Levke  (2000) NP-completeness notions under strong hypotheses.  [Dissertation]     
relation: https://archiv.ub.uni-heidelberg.de/volltextserver/1384/
rights: info:eu-repo/semantics/openAccess
rights: http://archiv.ub.uni-heidelberg.de/volltextserver/help/license_urhg.html
language: eng