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

Weak Completeness Notions for Exponential Time

Bakibayev, Timur

German Title: Allgemeinere schwache Vollständigkeitsbegriffe für E und EXP

PDF, English
Download (655kB) | Lizenz: Print on Demand

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.


Abstract The standard way for proving a problem to be intractable is to show that the problem is hard or complete for one of the standard complexity classes containing intractable problems. Lutz (1995) proposed a generalization of this approach by introducing more general weak hardness notions which still imply intractability. While a set A is hard for a class C if all problems in C can be reduced to A (by a polynomial-time bounded many-one reduction) and complete if it is hard and a member of C, Lutz proposed to call a set A weakly hard if a nonnegligible part of C can be reduced to A and to call A weakly complete if in addition A 2 C. For the exponential-time classes E = DTIME(2lin) and EXP = DTIME(2poly), Lutz formalized these ideas by introducing resource bounded (Lebesgue) measures on these classes and by saying that a subclass of E is negligible if it has measure 0 in E (and similarly for EXP). A variant of these concepts, based on resource bounded Baire category in place of measure, was introduced by Ambos-Spies (1996) where now a class is declared to be negligible if it is meager in the corresponding resource bounded sense. In our thesis we introduce and investigate new, more general, weak hardness notions for E and EXP and compare them with the above concepts from the literature. The two main new notions we introduce are nontriviality, which may be viewed as the most general weak hardness notion, and strong nontriviality. In case of E, a set A is E-nontrivial if, for any k 1, A has a predecessor in E which is 2kn complex, i.e., which can only be computed by Turing machines with run times exceeding 2kn on infinitely many inputs; and A is strongly E-nontrivial if there are predecessors which are almost everywhere 2kn complex. Besides giving examples and structural properties of the E-(non)trivial and strongly E-(non)trivial sets, we separate all weak hardness concepts for E, compare the corresponding concepts for E and EXP, answer the question whether (strongly) E-nontrivial sets are typical among the sets in E (or among the computable sets, or among all sets), investigate the degrees of the (strongly) E-nontrivial sets, and analyze the strength of these concepts if we replace the underlying p-m-reducibility by some weaker polynomial-time reducibilities.

Translation of abstract (German)

Zusammenfassung Will man zeigen, dass ein Problem zwar algorithmisch lösbar, aber nur schwer (d.h. nicht in Polynomialzeit) lösbar ist, so macht man dies meist dadurch, dass man das Problem als hart oder vollständig für eine Komplexitätsklasse nachweist, die schwer lösbare Probleme enthält. Lutz (1995) schlug eine Verallgemeinerung dieses Ansatzes vor, die auf schwachen Härte- bzw. Vollständigkeitsbegriffen basiert. Während eine Menge A hart (oder schwer) für eine Komplexitätsklasse C ist, wenn alle Probleme aus C auf A reduziert werden können (mittels einer polynomialzeit-bechränkten many-one-Reduktion) und A vollständig für C ist, wenn zusätzlich A selbst in C liegt, nennt Lutz eine Menge A schwach hart, falls ein nicht zu vernachlässigender Teil der Probleme aus C auf A reduzierbar ist, und schwach vollständig, wenn wiederum zusätzlich A 2 C gilt. Im Falle der Exponentialzeit-Klassen E=DTIME(2lin) und EXP=DTIME(2poly) formalisierte Lutz diese Ideen, indem er geeignete ressourcenbeschränkte Varianten des Lebesgue-Maßes auf diesen Klassen einführte und Teilklassen von E vernachlässigbar nennt, falls diese Maß 0 in E haben (und entsprechend für EXP). Eine Variante dieser Konzepte, in der das Lebesgue-Maß durch Baire-Kategorie ersetzt ist, wurde von Ambos-Spies (1996) vorgeschlagen. Hier sind die vernachlässigbaren Teilklassen diejenigen, die - im entsprechenden ressourcenbeschr¨ankten Sinne - mager sind. In unserer Dissertation führen wir neue, allgemeinere schwache Härtebegriffe für E und EXP ein und vergleichen diese mit den oben genannten Konzepten aus der Literatur. Die zwei wichtigsten der von uns neu eingeführten Konzepte sind die Nichttrivialität, die als das allgemeinste schwache Härtekonzept angesehen werden kann, und die starke Nichttrivialität. Im Falle der Klasse E ist eine Menge A E-nichttrivial, falls es für jedes k 1 eine Menge aus E gibt, die auf A reduzierbar ist und 2knkomplex ist, d.h. nur von Turingmaschinen erkannt werden kann, deren Laufzeit auf unendlich vielen Eingaben die Schranke 2kn überschreitet; und A ist stark Enichttrivial, falls diese einen fast überall 2kn-komplexen Vorgänger in E besitzt. In unserer Arbeit geben wir Beispiele für E-(nicht)triviale und stark E-(nicht)triviale Mengen an, untersuchen deren Eigenschaften, trennen alle schwachen Vollständigkeitsbegriffe für E, vergleichen die entsprechenden Begriffe für E und EXP, beantworten die Frage, ob (stark) E-nichttriviale Mengen typisch sind (im Bezug auf E, im Bezug auf die entscheidbaren Mengen und im Bezug auf alle Mengen), untersuchen die (p-m-)Grade der (stark) E-(nicht)trivialen Mengen, und analysieren die Stärke der Varianten der schwachen Härtebegriffe, bei denen die zugrundegelegte p-m-Reduzierbarkeit durch allgemeinere Polynomialzeit-Reduzierbarkeiten ersetzt ist.

Item Type: Dissertation
Supervisor: Ambos-Spies, Prof. Dr. Klaus
Date of thesis defense: 10 March 2010
Date Deposited: 18 Mar 2010 15:01
Date: 2010
Faculties / Institutes: The Faculty of Mathematics and Computer Science > Department of Computer Science
Subjects: 004 Data processing Computer science
Controlled Keywords: Hardness, Completeness, Complexity, Exponential, Time
Uncontrolled Keywords: Vollständigkeit , E und EXPHardness , Completeness , Complexity , Exponential , Time
About | FAQ | Contact | Imprint |
OA-LogoDINI certificate 2013Logo der Open-Archives-Initiative