NL-printable sets and nondeterministic Kolmogorov complexity

AbstractP-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