Affordable Access

Publisher Website

NL-printable sets and Nondeterministic Kolmogorov Complexity

Authors
Journal
Electronic Notes in Theoretical Computer Science
1571-0661
Publisher
Elsevier
Publication Date
Volume
84
Identifiers
DOI: 10.1016/s1571-0661(04)80838-7

Abstract

Abstract This paper introduces nondeterministic space-bounded Kolmogorov complexity, and we show that it has some nice properties not shared by some other resource-bounded notions of K-complexity. P-printable sets were defined by Hartmanis and Yesha and have been investigated by several researchers. The analogous notion of L-printable sets was defined by Fortnow et al; both P-printability and L-printability were shown to be related to notions of resource-bounded Kolmogorov complexity. NL-printability was defined by Jenner and Kirsig, but some basic questions regarding this notion were left open. In this paper we answer a question of Jenner and Kirsig by providing a machine-based characterization of the NL-printable sets.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

NL-printable sets and nondeterministic Kolmogorov...

on Theoretical Computer Science Jan 01, 2006

Kolmogorov complexity of enumerating finite sets

on Information Processing Letters Jan 01, 2007

Kolmogorov complexity and degrees of tally sets

on Information and Computation Jan 01, 1990

Kolmogorov complexity and computably enumerable se...

on Annals of Pure and Applied Log...
More articles like this..