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 |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Gesehen am 29.06.2021 Published: 17 May 2012 |
| Beschreibung: | Online Resource |
| ISSN: | 1433-0490 |
| DOI: | 10.1007/s00224-012-9413-4 |