Weak completeness notions for exponential time
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 lin...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
04 April 2019
|
| In: |
Theory of computing systems
Year: 2019, Volume: 63, Issue: 6, Pages: 1388-1412 |
| ISSN: | 1433-0490 |
| DOI: | 10.1007/s00224-019-09920-4 |
| Online Access: | Verlag, Volltext: https://doi.org/10.1007/s00224-019-09920-4 Verlag: https://doi.org/10.1007/s00224-019-09920-4 
|
| Author Notes: | Klaus Ambos-Spies, Timur Bakibayev |
| Summary: | 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. |
|---|---|
| Item Description: | Gesehen am 15.01.2020 |
| Physical Description: | Online Resource |
| ISSN: | 1433-0490 |
| DOI: | 10.1007/s00224-019-09920-4 |