Time-bounded Kolmogorov complexity and Solovay functions
A Solovay function is an upper bound g for prefix-free Kolmogorov complexity K that is nontrivial in the sense that g agrees with K, up to some additive constant, on infinitely many places n. We obtain natural examples of computable Solovay functions by showing that for some constant c0 and all comp...
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
2013
|
| In: |
Theory of computing systems
Year: 2013, Jahrgang: 52, Heft: 1, Pages: 80-94 |
| ISSN: | 1433-0490 |
| DOI: | 10.1007/s00224-012-9413-4 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1007/s00224-012-9413-4
|
| Verfasserangaben: | Rupert Hölzl, Thorsten Kräling, Wolfgang Merkle |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1761444395 | ||
| 003 | DE-627 | ||
| 005 | 20240414193212.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 210629s2013 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1007/s00224-012-9413-4 |2 doi | |
| 035 | |a (DE-627)1761444395 | ||
| 035 | |a (DE-599)KXP1761444395 | ||
| 035 | |a (OCoLC)1341417822 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Hölzl, Rupert |e VerfasserIn |0 (DE-588)143327291 |0 (DE-627)704454890 |0 (DE-576)336473923 |4 aut | |
| 245 | 1 | 0 | |a Time-bounded Kolmogorov complexity and Solovay functions |c Rupert Hölzl, Thorsten Kräling, Wolfgang Merkle |
| 264 | 1 | |c 2013 | |
| 300 | |a 15 | ||
| 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 29.06.2021 | ||
| 500 | |a Published: 17 May 2012 | ||
| 520 | |a A Solovay function is an upper bound g for prefix-free Kolmogorov complexity K that is nontrivial in the sense that g agrees with K, up to some additive constant, on infinitely many places n. We obtain natural examples of computable Solovay functions by showing that for some constant c0 and all computable functions t such that c0n≤t(n), the time-bounded version Ktof K is a Solovay function. | ||
| 700 | 1 | |a Kräling, Thorsten |e VerfasserIn |0 (DE-588)1049899121 |0 (DE-627)782854052 |0 (DE-576)403882931 |4 aut | |
| 700 | 1 | |a Merkle, Wolfgang |e VerfasserIn |0 (DE-588)1049898400 |0 (DE-627)782852831 |0 (DE-576)40388201X |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Theory of computing systems |d New York, NY : Springer, 1997 |g 52(2013), 1, Seite 80-94 |h Online-Ressource |w (DE-627)254909728 |w (DE-600)1463181-7 |w (DE-576)074754165 |x 1433-0490 |7 nnas |a Time-bounded Kolmogorov complexity and Solovay functions |
| 773 | 1 | 8 | |g volume:52 |g year:2013 |g number:1 |g pages:80-94 |g extent:15 |a Time-bounded Kolmogorov complexity and Solovay functions |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s00224-012-9413-4 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20210629 | ||
| 993 | |a Article | ||
| 994 | |a 2013 | ||
| 998 | |g 1049898400 |a Merkle, Wolfgang |m 1049898400:Merkle, Wolfgang |d 110000 |d 110300 |e 110000PM1049898400 |e 110300PM1049898400 |k 0/110000/ |k 1/110000/110300/ |p 4 | ||
| 998 | |g 1049899121 |a Kräling, Thorsten |m 1049899121:Kräling, Thorsten |d 110000 |d 110300 |e 110000PK1049899121 |e 110300PK1049899121 |k 0/110000/ |k 1/110000/110300/ |p 3 |y j | ||
| 998 | |g 143327291 |a Hölzl, Rupert |m 143327291:Hölzl, Rupert |d 110000 |d 110300 |e 110000PH143327291 |e 110300PH143327291 |k 0/110000/ |k 1/110000/110300/ |p 2 | ||
| 999 | |a KXP-PPN1761444395 |e 3941927418 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"name":{"displayForm":["Rupert Hölzl, Thorsten Kräling, Wolfgang Merkle"]},"id":{"eki":["1761444395"],"doi":["10.1007/s00224-012-9413-4"]},"origin":[{"dateIssuedDisp":"2013","dateIssuedKey":"2013"}],"relHost":[{"physDesc":[{"extent":"Online-Ressource"}],"origin":[{"dateIssuedDisp":"1997-","publisher":"Springer ; Springer","dateIssuedKey":"1997","publisherPlace":"New York, NY ; [Berlin ; Heidelberg]"}],"id":{"issn":["1433-0490"],"zdb":["1463181-7"],"eki":["254909728"]},"pubHistory":["30.1997 -"],"part":{"pages":"80-94","issue":"1","year":"2013","extent":"15","text":"52(2013), 1, Seite 80-94","volume":"52"},"type":{"media":"Online-Ressource","bibl":"periodical"},"disp":"Time-bounded Kolmogorov complexity and Solovay functionsTheory of computing systems","note":["Gesehen am 08.05.07"],"language":["eng"],"recId":"254909728","title":[{"title":"Theory of computing systems","title_sort":"Theory of computing systems"}]}],"physDesc":[{"extent":"15 S."}],"person":[{"role":"aut","display":"Hölzl, Rupert","roleDisplay":"VerfasserIn","given":"Rupert","family":"Hölzl"},{"given":"Thorsten","family":"Kräling","role":"aut","roleDisplay":"VerfasserIn","display":"Kräling, Thorsten"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Merkle, Wolfgang","given":"Wolfgang","family":"Merkle"}],"title":[{"title":"Time-bounded Kolmogorov complexity and Solovay functions","title_sort":"Time-bounded Kolmogorov complexity and Solovay functions"}],"language":["eng"],"recId":"1761444395","type":{"bibl":"article-journal","media":"Online-Ressource"},"note":["Gesehen am 29.06.2021","Published: 17 May 2012"]} | ||
| SRT | |a HOELZLRUPETIMEBOUNDE2013 | ||