Paper Info
Title
A Relation Between Sparse and Printable Sets in NSPACE(log n)
Abstract
For the polynomial time classes NPsparse and NPprint it is known that these classes coincide if and only if nondeterministic exponential time is closed under complement ([Ha Ye 84]). Transfering this result to logarithmic space classes would lead to an equality of sparse and printable sets in NSPACE(log n) if and only if nondeterministic space classes are closed under complement. We know that space classes are closed under complement, so unfortunately the techniques that work in the polynomial time case are useless for logarithmic space. In this paper we want to investigate some relations between sparse sets and printable sets in NSPACE(log n). We show that separating NL-printable sets from those sparse sets in NSPACE(log n) that can be recognized by 1-way machines also separates 2-way sparse sets from these 1-way sets.
Year
DOI
Venue
1997
10.1007/BFb0052086
Foundations of Computer Science: Potential - Theory - Cognition
Keywords
Field
DocType
printable sets,log n,polynomial time
Discrete mathematics,Binary logarithm,Combinatorics,Exponential function,Nondeterministic algorithm,NSPACE,If and only if,Time complexity,Logarithmic space,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-63746-X
0
0.34
References 
Authors
9
1
Name
Order
Citations
PageRank
Bernd Kirsig1182.41