TY  - GEN
A1  - Bakibayev, Timur
N2  - 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.
AV  - public
UR  - https://archiv.ub.uni-heidelberg.de/volltextserver/10499/
TI  - Weak Completeness Notions for Exponential Time
KW  - Vollständigkeit 
KW  -  E und EXPHardness 
KW  -  Completeness 
KW  -  Complexity 
KW  -  Exponential 
KW  -  Time
Y1  - 2010///
ID  - heidok10499
ER  -