eprintid: 1384
rev_number: 8
eprint_status: archive
userid: 1
dir: disk0/00/00/13/84
datestamp: 2000-11-20 00:00:00
lastmod: 2014-04-03 10:40:22
status_changed: 2012-08-14 15:01:06
type: doctoralThesis
metadata_visibility: show
creators_name: Bentzien, Levke
title: NP-completeness notions under strong hypotheses
title_de: NP-Vollständigkeitsbegriffe unter starken Annahmen
ispublished: pub
subjects: ddc-510
divisions: i-110400
adv_faculty: af-11
keywords: Generizität , ressourcenbeschränktcomplexity, nondeterminism , completeness , resource-bounded , genericity
cterms_swd: Komplexitätstheorie
cterms_swd: Nichtdeterminismus
cterms_swd: Vollständigkeit
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.
abstract_translated_lang: eng
class_scheme: msc
class_labels: 68Q15
date: 2000
date_type: published
id_scheme: DOI
id_number: 10.11588/heidok.00001384
ppn_swb: 1643181726
own_urn: urn:nbn:de:bsz:16-opus-13840
date_accepted: 2000-05-30
advisor: HASH(0x55fc36bfae18)
language: eng
bibsort: BENTZIENLENPCOMPLETE2000
full_text_status: public
citation:   Bentzien, Levke  (2000) NP-completeness notions under strong hypotheses.  [Dissertation]     
document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/1384/1/NPCompleteness.pdf