Navigation überspringen
Universitätsbibliothek Heidelberg
Status: Bibliographieeintrag

Verfügbarkeit
Standort: ---
Exemplare: ---
heiBIB
 Online-Ressource
Verfasst von:Ambos-Spies, Klaus [VerfasserIn]   i
 Bakibayev, Timur [VerfasserIn]   i
Titel:Weak completeness notions for exponential time
Verf.angabe:Klaus Ambos-Spies, Timur Bakibayev
E-Jahr:2019
Jahr:04 April 2019
Umfang:25 S.
Fussnoten:Gesehen am 15.01.2020
Titel Quelle:Enthalten in: Theory of computing systems
Ort Quelle:New York, NY : Springer, 1997
Jahr Quelle:2019
Band/Heft Quelle:63(2019), 6, Seite 1388-1412
ISSN Quelle:1433-0490
Abstract:Lutz (SIAM J. Comput. 24(6), 1170-1189, 1995) proposed the following generalization of hardness: While a problem A is hard for a complexity class C if all problems in C can be reduced to A, Lutz calls a problem weakly hard if a nonnegligible part of the problems in C can be reduced to A. For the linear exponential time class E = DTIME(2lin), Lutz formalized these ideas by introducing a resource-bounded (pseudo) measure on this class and by saying that a subclass of E is negligible if it has measure 0 in E. In this paper we introduce two new weak hardness notions for E - E-nontriviality and strongly E-nontriviality. They generalize Lutz’s weak hardness notion for E, but are much simpler conceptually. Namely, a set A is E-nontrivial if, for any k ≥ 1, there is a set Bk ∈E which can be reduced to A (by a polynomial time many-one reduction) and which cannot be computed in time O(2kn), and a set A is strongly E-nontrivial if the set Bk can be chosen to be almost everywhereO(2kn)-complex, i.e. if Bk can be chosen such that any algorithm that computes Bk runs for more than 2k|x| steps on all but finitely many inputs x.
DOI:doi:10.1007/s00224-019-09920-4
URL:Bitte beachten Sie: Dies ist ein Bibliographieeintrag. Ein Volltextzugriff für Mitglieder der Universität besteht hier nur, falls für die entsprechende Zeitschrift/den entsprechenden Sammelband ein Abonnement besteht oder es sich um einen OpenAccess-Titel handelt.

Volltext: https://doi.org/10.1007/s00224-019-09920-4
 Verlag: https://doi.org/10.1007/s00224-019-09920-4
 DOI: https://doi.org/10.1007/s00224-019-09920-4
Datenträger:Online-Ressource
Sprache:eng
Sach-SW:Almost everywhere complexity
 Completeness
 Exponential time
 Resource-bounded measure
 Weak completeness
K10plus-PPN:1687445257
Verknüpfungen:→ Zeitschrift

Permanenter Link auf diesen Titel (bookmarkfähig):  https://katalog.ub.uni-heidelberg.de/titel/68476610   QR-Code
zum Seitenanfang