NL-printable sets and nondeterministic Kolmogorov 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. Nondeterministic logspace (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. In order to relate NL-printability to resource-bounded Kolmogorov complexity, the paper introduces nondeterministic space-bounded Kolmogorov complexity. We present some of the basic properties of this notion of Kolmogorov complexity. Using similar techniques, we investigate relationships among classes between NL and UL. (c) 2006 Elsevier B.V. All rights reserved.
nl-printability kolmogorov complexity unambiguous logspace