Weak completeness notions for exponential time

• Verfasst von: Ambos-Spies, Klaus [VerfasserIn]
• Verfasst von: Bakibayev, Timur [VerfasserIn]
• 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
• DOI: doi:10.1007/s00224-019-09920-4
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: Almost everywhere complexity
• Sach-SW: Completeness
• Sach-SW: Exponential time
• Sach-SW: Resource-bounded measure
• Sach-SW: Weak completeness
• K10plus-PPN: 1687445257

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.