Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
NL-printable sets and nondeterministic Kolmogorov complexity
Allender E. Theoretical Computer Science355 (2):127-138,2006.Type:Article
Date Reviewed: Sep 22 2006

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.

Reviewer:  Lane A. Hemaspaandra Review #: CR133332 (0707-0693)
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.
Bookmark and Share
  Reviewer Selected
 
 
Bounded-Action Devices (F.1.1 ... )
 
 
Alternation And Nondeterminism (F.1.2 ... )
 
 
Relations Between Models (F.1.1 ... )
 
 
Models Of Computation (F.1.1 )
 
 
Modes Of Computation (F.1.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Bounded-Action Devices": Date
Fairness and conspiracies
Best E. Information Processing Letters 18(4): 215-220, 1984. Type: Article
May 1 1985
Separating the eraser Turing machine classes Le, NLe, co-NLe and Pe
Krause M., Meinel C., Waack S. Theoretical Computer Science 86(2): 267-275, 1991. Type: Article
Jul 1 1992
Two nonlinear lower bounds for on-line computations
Dūris P., Galil Z., Paul W. (ed), Reischuk R. Information and Control 60(1-3): 1-11, 1984. Type: Article
Aug 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy