NL-printable sets and Nondeterministic Kolmogorov Complexity

详细信息    查看全文

• 作者：Eric Allender
• 刊名：Electronic Notes in Theoretical Computer Science
• 出版年：2003
• 出版时间：September 2003
• 年：2003
• 卷：84
• 期：Complete
• 页码：1-15
• 全文大小：931 K

文摘

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.