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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
2013
|
| In: |
Theory of computing systems
Year: 2013, Volume: 52, Issue: 1, Pages: 80-94 |
| ISSN: | 1433-0490 |
| DOI: | 10.1007/s00224-012-9413-4 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1007/s00224-012-9413-4
|
| Author Notes: | Rupert Hölzl, Thorsten Kräling, Wolfgang Merkle |
| Summary: | 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. |
|---|---|
| Item Description: | Gesehen am 29.06.2021 Published: 17 May 2012 |
| Physical Description: | Online Resource |
| ISSN: | 1433-0490 |
| DOI: | 10.1007/s00224-012-9413-4 |