Status: Bibliographieeintrag
Standort: ---
Exemplare:
---
| |  Online-Ressource |
|---|
| Verfasst von: | Hölzl, Rupert [VerfasserIn]  |
|---|
| | Kräling, Thorsten [VerfasserIn] |
|---|
| | Merkle, Wolfgang [VerfasserIn] |
|---|
| Titel: | Time-bounded Kolmogorov complexity and Solovay functions |
|---|
| Verf.angabe: | Rupert Hölzl, Thorsten Kräling, Wolfgang Merkle |
|---|
| Jahr: | 2013 |
|---|
| Umfang: | 15 S. |
|---|
| Fussnoten: | Gesehen am 29.06.2021 ; Published: 17 May 2012 |
|---|
| Titel Quelle: | Enthalten in: Theory of computing systems |
|---|
| Ort Quelle: | New York, NY : Springer, 1997 |
|---|
| Jahr Quelle: | 2013 |
|---|
| Band/Heft Quelle: | 52(2013), 1, Seite 80-94 |
|---|
| ISSN Quelle: | 1433-0490 |
|---|
| Abstract: | 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. |
|---|
| DOI: | doi:10.1007/s00224-012-9413-4 |
|---|
| URL: | Bitte beachten Sie: Dies ist ein Bibliographieeintrag. Ein Volltextzugriff für Mitglieder der Universität besteht hier nur, falls für die entsprechende Zeitschrift/den entsprechenden Sammelband ein Abonnement besteht oder es sich um einen OpenAccess-Titel handelt.
Volltext: https://doi.org/10.1007/s00224-012-9413-4 |
|---|
| | DOI: https://doi.org/10.1007/s00224-012-9413-4 |
|---|
| Datenträger: | Online-Ressource |
|---|
| Sprache: | eng |
|---|
| K10plus-PPN: | 1761444395 |
|---|
| Verknüpfungen: | → Zeitschrift |
|---|
Time-bounded Kolmogorov complexity and Solovay functions / Hölzl, Rupert [VerfasserIn]; 2013 (Online-Ressource)
68753908
