New problems complete for nondeterministic log space | Theory of Computing Systems Skip to main content
Springer Nature Link
Log in

New problems complete for nondeterministic log space

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

It is shown that a variety of problems have computational complexity equivalent to that of finding a path through a directed graph. These results, which parallel those of Karp at a lower complexity level, concern satisfiability of propositional formulas with two literals per clause, generation of elements by an associative binary operation, solution of linear equations with two variables per equation, equivalence of generalized sequential machines with final states, and deciding theLL(k) andLR(k) conditions for context-free grammars. Finally, several problems are shown equivalent to reachability in undirected graphs, including bipartiteness and satisfiability of formulas with the “exclusive or” connective.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aho, A. V.;Ullman, J. D. The theory of parsing, translation and compiling. Vol. 1: Parsing. Prentice Hall, Englewood Cliffs, New Jersey. 1972.

    Google Scholar 

  2. Cook, S. A. The complexity of theorem proving procedures.Proceedings of 3rd Annual ACM Symposium on Theory of Computing, pp. 151–158, 1971.

  3. Chang, C. L.;Lee, R. C. T. Symbolic logic and Mechanical theorem proving. Academic Press, New York, 1973.

    Google Scholar 

  4. Griffiths, T. V. The unsolvability of the equivalence problem forλ-free nondeterministic generalized sequential machines.Journal of the ACM 15 (1968), 409–413.

    Google Scholar 

  5. Hartmanis, J.; Hunt, H. B. III. The LBA problem and its importance in the theory of computing. Computer Science Technical Report TR-171, Cornell University, 1973.

  6. Hartmanis, J.; Simon, J. On the structure of feasible computations. Computer Science Technical Report TR-74-210, Cornell University, 1974.

  7. Hunt, H. B. III;Szymanski, T.; Ullman, J. D. On the complexity ofLR(k) testing.Proceedings of 2nd Annual ACM Symposium on Principles of Programming Languages, pp. 130–138, 1975.

  8. Jones, N. D. Space-bounded reducibility among combinatorial problems.Journal of Computer and Systems Sciences 11 (1975), 68–75.

    Google Scholar 

  9. Jones, N. D.; Laaser, W. T. Problems complete for deterministic polynomial time. To appear inTheoretical Computer Science.

  10. Karp, R. M. Reducibility among combinatorial problems. InComplexity of Computer Computations, edited by R. E. Miller and J. Thatcher, Plenum Press, New York, pp. 85–104, 1972.

    Google Scholar 

  11. Lynch, N. Personal communication.

  12. Savitch, W. J. Relations between nondeterministic and deterministic tape complexities.Journal of Computer and Systems Sciences 4 (1970), 177–192.

    Google Scholar 

  13. Savitch, W. J. Nondeterministic LogN space.Proceedings of 8th Princeton Conference on Information Sciences and Systems. Princeton University, pp. 21–23, 1974.

  14. Sudborough, I. H. Personal Communication.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Kansas, 66045, Lawrence, Kansas, USA

    Neil D. Jones & Y. Edmund Lien

  2. Department of Computer Science, Stanford University, 94305, Palo Alto, California, USA

    William T. Laaser

Authors
  1. Neil D. Jones
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Y. Edmund Lien
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. William T. Laaser
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The work of this author was partly supported by Kansas General Research Grant 3756-5038. A preliminary version appears in the Proceedings of the Eighth Princeton Conference on Information Sciences and Systems, Princeton University, pp. 184–188, March 1974.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jones, N.D., Lien, Y.E. & Laaser, W.T. New problems complete for nondeterministic log space. Math. Systems Theory 10, 1–17 (1976). https://doi.org/10.1007/BF01683259

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01683259

Keywords

Search

Navigation