Computing Reviews

NL-printable sets and nondeterministic Kolmogorov complexity
Allender E. Theoretical Computer Science355(2):127-138,2006.Type:Article
Date Reviewed: 09/22/06

The study of printability (namely, polynomial time (P) printability) was introduced by Hartmanis and Yesha [1]. Jenner and Kirsig [2] proved that every nondeterministic logspace (NL) printable set is a sparse set that is accepted by a 1-NL machine. This paper proves the converse, and a number of other interesting results regarding upward translation of equality, space-bounded Kolmogorov complexity, and space classes, via a hashing technique. The paper is clearly written, and even employs some sly humor.


1)

Hartmanis, J.; Yesha, Y. Computation times of NP sets of different densities. Theoretical Computer Science 34, (1984), 17–32.


2)

Jenner, B.; Kirsig, B. Alternierung und Logarithmischer Platz, Dissertation, University of Hamburg, 1989.

Reviewer:  Lane A. Hemaspaandra Review #: CR133332 (0707-0693)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy