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...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
04 April 2019
|
| In: |
Theory of computing systems
Year: 2019, Jahrgang: 63, Heft: 6, Pages: 1388-1412 |
| ISSN: | 1433-0490 |
| DOI: | 10.1007/s00224-019-09920-4 |
| Online-Zugang: | Verlag, Volltext: https://doi.org/10.1007/s00224-019-09920-4 Verlag: https://doi.org/10.1007/s00224-019-09920-4 
|
| Verfasserangaben: | Klaus Ambos-Spies, Timur Bakibayev |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1687445257 | ||
| 003 | DE-627 | ||
| 005 | 20220817204917.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 200115s2019 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1007/s00224-019-09920-4 |2 doi | |
| 035 | |a (DE-627)1687445257 | ||
| 035 | |a (DE-599)KXP1687445257 | ||
| 035 | |a (OCoLC)1341298156 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Ambos-Spies, Klaus |d 1951- |e VerfasserIn |0 (DE-588)141551607 |0 (DE-627)629951861 |0 (DE-576)16006810X |4 aut | |
| 245 | 1 | 0 | |a Weak completeness notions for exponential time |c Klaus Ambos-Spies, Timur Bakibayev |
| 264 | 1 | |c 04 April 2019 | |
| 300 | |a 25 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 15.01.2020 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a Almost everywhere complexity | |
| 650 | 4 | |a Completeness | |
| 650 | 4 | |a Exponential time | |
| 650 | 4 | |a Resource-bounded measure | |
| 650 | 4 | |a Weak completeness | |
| 700 | 1 | |a Bakibayev, Timur |e VerfasserIn |0 (DE-588)140976795 |0 (DE-627)703847023 |0 (DE-576)321269721 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Theory of computing systems |d New York, NY : Springer, 1997 |g 63(2019), 6, Seite 1388-1412 |h Online-Ressource |w (DE-627)254909728 |w (DE-600)1463181-7 |w (DE-576)074754165 |x 1433-0490 |7 nnas |a Weak completeness notions for exponential time |
| 773 | 1 | 8 | |g volume:63 |g year:2019 |g number:6 |g pages:1388-1412 |g extent:25 |a Weak completeness notions for exponential time |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s00224-019-09920-4 |x Verlag |x Resolving-System |3 Volltext |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s00224-019-09920-4 |x Verlag |
| 951 | |a AR | ||
| 992 | |a 20200115 | ||
| 993 | |a Article | ||
| 994 | |a 2019 | ||
| 998 | |g 141551607 |a Ambos-Spies, Klaus |m 141551607:Ambos-Spies, Klaus |d 110000 |d 110300 |e 110000PA141551607 |e 110300PA141551607 |k 0/110000/ |k 1/110000/110300/ |p 1 |x j | ||
| 999 | |a KXP-PPN1687445257 |e 3575576726 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"person":[{"family":"Ambos-Spies","given":"Klaus","roleDisplay":"VerfasserIn","display":"Ambos-Spies, Klaus","role":"aut"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Bakibayev, Timur","given":"Timur","family":"Bakibayev"}],"title":[{"title":"Weak completeness notions for exponential time","title_sort":"Weak completeness notions for exponential time"}],"type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Gesehen am 15.01.2020"],"recId":"1687445257","language":["eng"],"name":{"displayForm":["Klaus Ambos-Spies, Timur Bakibayev"]},"origin":[{"dateIssuedKey":"2019","dateIssuedDisp":"04 April 2019"}],"id":{"doi":["10.1007/s00224-019-09920-4"],"eki":["1687445257"]},"physDesc":[{"extent":"25 S."}],"relHost":[{"part":{"text":"63(2019), 6, Seite 1388-1412","volume":"63","extent":"25","year":"2019","issue":"6","pages":"1388-1412"},"pubHistory":["30.1997 -"],"language":["eng"],"recId":"254909728","type":{"bibl":"periodical","media":"Online-Ressource"},"note":["Gesehen am 08.05.07"],"disp":"Weak completeness notions for exponential timeTheory of computing systems","title":[{"title":"Theory of computing systems","title_sort":"Theory of computing systems"}],"physDesc":[{"extent":"Online-Ressource"}],"id":{"issn":["1433-0490"],"zdb":["1463181-7"],"eki":["254909728"]},"origin":[{"publisherPlace":"New York, NY ; [Berlin ; Heidelberg]","dateIssuedDisp":"1997-","dateIssuedKey":"1997","publisher":"Springer ; Springer"}]}]} | ||
| SRT | |a AMBOSSPIESWEAKCOMPLE0420 | ||