Genericity and measure for exponential time
Recently, Lutz [14, 15] introduced a polynomial time bounded version of Lebesgue measure. He and others (see e.g. [11, 13-18, 20]) used this concept to investigate the quantitative structure of Exponential Time (E = DTIME(2lin)). Previously, Ambos-Spies et al. [2, 3] introduced polynomial time bound...
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
10 November 1996
|
| In: |
Theoretical computer science
Year: 1996, Jahrgang: 168, Heft: 1, Pages: 3-19 |
| ISSN: | 1879-2294 |
| DOI: | 10.1016/0304-3975(96)89424-2 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/0304-3975(96)89424-2 Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/0304397596894242 
|
| Verfasserangaben: | Klaus Ambos-Spies, Hans-Christian Neis, Sebastiaan A. Terwijn |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1843128055 | ||
| 003 | DE-627 | ||
| 005 | 20230710180456.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 230419s1996 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1016/0304-3975(96)89424-2 |2 doi | |
| 035 | |a (DE-627)1843128055 | ||
| 035 | |a (DE-599)KXP1843128055 | ||
| 035 | |a (OCoLC)1389826044 | ||
| 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 Genericity and measure for exponential time |c Klaus Ambos-Spies, Hans-Christian Neis, Sebastiaan A. Terwijn |
| 264 | 1 | |c 10 November 1996 | |
| 300 | |a 17 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Elektronische Reproduktion der Druck-Ausgabe 16. Februar 1999 | ||
| 500 | |a Gesehen am 19.04.2023 | ||
| 520 | |a Recently, Lutz [14, 15] introduced a polynomial time bounded version of Lebesgue measure. He and others (see e.g. [11, 13-18, 20]) used this concept to investigate the quantitative structure of Exponential Time (E = DTIME(2lin)). Previously, Ambos-Spies et al. [2, 3] introduced polynomial time bounded genericity concepts and used them for the investigation of structural properties of NP (under appropriate assumptions) and E. Here we relate these concepts to each other. We show that, for any c ⩾ 1, the class of nc-generic sets has p-measure 1. This allows us to simplify and extend certain p-measure 1-results. To illustrate the power of generic sets we take the Small Span Theorem of Juedes and Lutz [11] as an example and prove a generalization for bounded query reductions. | ||
| 700 | 1 | |a Neis, Hans-Christian |e VerfasserIn |0 (DE-588)1286603595 |0 (DE-627)184312856X |4 aut | |
| 700 | 1 | |a Terwijn, Sebastiaan A. |e VerfasserIn |0 (DE-588)140769552 |0 (DE-627)703782266 |0 (DE-576)320698742 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Theoretical computer science |d Amsterdam [u.a.] : Elsevier, 1975 |g 168(1996), 1, Seite 3-19 |h Online-Ressource |w (DE-627)265784174 |w (DE-600)1466347-8 |w (DE-576)074891030 |x 1879-2294 |7 nnas |a Genericity and measure for exponential time |
| 773 | 1 | 8 | |g volume:168 |g year:1996 |g number:1 |g pages:3-19 |g extent:17 |a Genericity and measure for exponential time |
| 856 | 4 | 0 | |u https://doi.org/10.1016/0304-3975(96)89424-2 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://www.sciencedirect.com/science/article/pii/0304397596894242 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20230419 | ||
| 993 | |a Article | ||
| 994 | |a 1996 | ||
| 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-PPN1843128055 |e 4311193580 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"name":{"displayForm":["Klaus Ambos-Spies, Hans-Christian Neis, Sebastiaan A. Terwijn"]},"id":{"eki":["1843128055"],"doi":["10.1016/0304-3975(96)89424-2"]},"origin":[{"dateIssuedKey":"1996","dateIssuedDisp":"10 November 1996"}],"relHost":[{"origin":[{"publisherPlace":"Amsterdam [u.a.]","dateIssuedDisp":"1975-","dateIssuedKey":"1975","publisher":"Elsevier"}],"id":{"zdb":["1466347-8"],"eki":["265784174"],"issn":["1879-2294"]},"physDesc":[{"extent":"Online-Ressource"}],"title":[{"title":"Theoretical computer science","subtitle":"the journal of the EATCS","title_sort":"Theoretical computer science"}],"disp":"Genericity and measure for exponential timeTheoretical computer science","type":{"media":"Online-Ressource","bibl":"periodical"},"note":["Gesehen am 12.04.23"],"recId":"265784174","language":["eng"],"pubHistory":["1.1975/76 - 412.2011; Vol. 413.2012 -"],"part":{"text":"168(1996), 1, Seite 3-19","volume":"168","extent":"17","year":"1996","issue":"1","pages":"3-19"}}],"physDesc":[{"extent":"17 S."}],"person":[{"roleDisplay":"VerfasserIn","display":"Ambos-Spies, Klaus","role":"aut","family":"Ambos-Spies","given":"Klaus"},{"given":"Hans-Christian","family":"Neis","role":"aut","roleDisplay":"VerfasserIn","display":"Neis, Hans-Christian"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Terwijn, Sebastiaan A.","given":"Sebastiaan A.","family":"Terwijn"}],"title":[{"title":"Genericity and measure for exponential time","title_sort":"Genericity and measure for exponential time"}],"recId":"1843128055","language":["eng"],"type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Elektronische Reproduktion der Druck-Ausgabe 16. Februar 1999","Gesehen am 19.04.2023"]} | ||
| SRT | |a AMBOSSPIESGENERICITY1019 | ||