Time-bounded Kolmogorov complexity and Solovay functions
type: Item
instance of: scholarly article
title: Time-bounded Kolmogorov complexity and Solovay functions
zbMATH Open document ID: 1261.68077
author: Thorsten Kräling
author: Wolfgang Merkle
author: Rupert Hölzl
published in: Theory of Computing Systems
publication date: 2013-04-15T00:00:00Z
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 6153888
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: Solovay function
zbMATH Keywords: computational depth
zbMATH Keywords: Kummer's gap theorem
zbMATH Keywords: traceability
zbMATH Keywords: high degree
MaRDI profile type: Publication
full work available at URL: s00224-012-9413-4
OpenAlex ID: W2048167699
cites work: 𝐾-trivial degrees and the jump-traceability hierarchy
cites work: Q5588648
cites work: Kolmogorov Complexity and Solovay Functions
cites work: Strong jump-traceability. I: The computably enumerable case
cites work: Strong jump-traceability. II: \(K\)-triviality
cites work: Algorithmic Randomness and Complexity
cites work: Time-Bounded Kolmogorov Complexity and Solovay Functions
cites work: Computational depth and reducibility
cites work: Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
cites work: Randomness and recursive enumerability
cites work: An introduction to Kolmogorov complexity and its applications
cites work: The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
cites work: Q3611832
cites work: Process complexity and effective random tests
DOI: 10.1007/S00224-012-9413-4
description: scientific article; zbMATH DE number 6153888