Status: Bibliographieeintrag
Standort: ---
Exemplare:
---
| Online-Ressource |
Verfasst von: | Ambos-Spies, Klaus [VerfasserIn]  |
| 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 |
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 |
Weak completeness notions for exponential time / Ambos-Spies, Klaus [VerfasserIn]; 04 April 2019 (Online-Ressource)
68476610