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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
E. Allender: The complexity of sparse sets in P, Proc. of the 1st Structure in Complexity Theory Conference, 1986, Lect. Notes in Comput. Sci. 223, 1–11.
E. Allender, R.S. Rubinstein: P-printable sets, SIAM Journ. Comput. 17,6 (1988), 1193–1202.
P. Berman: Relationships between density and deterministic complexity on NP complete languages, 5th ICALP 1978, Udine, Italy, Lect. Notes in Comput. Sci. 62, 1978, 63–71.
P. Berman, J. Hartmanis: On isomorphisms and density of NP and other complete sets, SIAM Journ. of Computing 6 (1977), 305–322.
J. Cai, D. Sivakumar: The resolution of a Hartmanis conjecture, UBCS-TR 95-30, Computer Science Dept., University at Buffalo, 1995.
J. Cai, D. Sivakumar: Resolution of Hartmanis' Conjecture fo NL-hard sparse sets, UBSC-TR 95-40, Computer Science Dept., University at Buffalo, 1995
L. Fortnow, J. Goldsmith, M.A. Levy, S. Mahaney: L-printable sets, 11th Conference on Comput. Complexity, (1996), 97–106
S. Fortune: A note on sparse complete sets, SIAM Journ. of Computing 8 (1979), 431–433.
J. Hartmanis: On log-tape isomorphisms of complete sets, Theoretical Computer Science 7, (1978), 273–286.
J. Hartmanis: Some Observations about Relativizations of Space Bounded Computations, Bull. European Association for Theoretical Computer Science 33, (1988), 82–92.
J. Hartmanis, Y. Yesha: Computation times of NP sets of different densities, Theoretical Computer Science 34 (1984), 17–32.
J. Hopcroft, J. Ullman: Some results on tape-bounded Turing machines, Journal of the ACM 16, (1969), 168–177.
N. Immerman: Nondeterministic space is closed under complement, Techn. Report, Yale University, YALEU/DCS/TR 552, July 1987.
B. Jenner, B. Kirsig: Alternierung und logarithmischer Platz, Dissertation, FB Informatik, Universität Hamburg, 1989.
S.R. Mahaney: Sparse complete sets for NP: solution of a conjecture by Berman and Hartmanis, Journ. of Comput. System Sci. 25, (1982), 130–143.
R. Szelepcsényi: The method of forcing for nondeterministic automata, Bull. European Association for Theoretical Computer Science 33, (Oct 1987), 96–100.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kirsig, B. (1997). A relation between sparse and printable sets in NSPACE(log n). In: Freksa, C., Jantzen, M., Valk, R. (eds) Foundations of Computer Science. Lecture Notes in Computer Science, vol 1337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052086
Download citation
DOI: https://doi.org/10.1007/BFb0052086
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63746-2
Online ISBN: 978-3-540-69640-7
eBook Packages: Springer Book Archive