Directly to content
  1. Publishing |
  2. Search |
  3. Browse |
  4. Recent items rss |
  5. Open Access |
  6. Jur. Issues |
  7. DeutschClear Cookie - decide language by browser settings

NP-completeness notions under strong hypotheses

Bentzien, Levke

German Title: NP-Vollständigkeitsbegriffe unter starken Annahmen

[thumbnail of NPCompleteness.pdf]
PDF, English
Download (964kB) | Terms of use

Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the DOI, URN or the persistent URL below, as we can guarantee their long-time accessibility.


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.

Document type: Dissertation
Supervisor: Ambos-Spies, Prof. Dr. Klaus
Date of thesis defense: 30 May 2000
Date Deposited: 20 Nov 2000 00:00
Date: 2000
Faculties / Institutes: The Faculty of Mathematics and Computer Science > Institut für Mathematik
DDC-classification: 510 Mathematics
Controlled Keywords: Komplexitätstheorie, Nichtdeterminismus, Vollständigkeit
Uncontrolled Keywords: Generizität , ressourcenbeschränktcomplexity, nondeterminism , completeness , resource-bounded , genericity
About | FAQ | Contact | Imprint |
OA-LogoDINI certificate 2013Logo der Open-Archives-Initiative