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

[img]
Preview
PDF, English
Download (941Kb) | Terms of use

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

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.

Item 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 > Department of Mathematics
Subjects: 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-LogoLogo der Open-Archives-Initiative