[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Inclusion complete tally languages and the Hartmanis-Berman conjecture

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

Stimulated by the work of Hartmanis and Berman [5], we study the question of the existence of a tally languageL inNP such thatL is inP if and only ifP = NP. The method used is applicable to questions regarding the comparison of a wide range of pairs of classes of formal languages specified by machines whose computational resources are bounded in time or space.

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
£29.99 /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 (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. Book, Tally languages and complexity classes,Information and Control 26 (1974), 186–193.

    Google Scholar 

  2. R. Book, Comparing complexity classes,J. Computer System Sci. 9 (1974), 213–229.

    Google Scholar 

  3. R. Book, Translational lemmas, polynomial time, and (logn)j-space,Theoretical Computer Sci. 1 (1976), 215–226.

    Google Scholar 

  4. S. Cook, Characterizations of pushdown machines in terms of time-bounded computers,J. Assoc. Comput. Mach. 18 (1971), 4–18.

    Google Scholar 

  5. J. Hartmanis and L. Berman, On isomorphisms and density ofNP and other complete sets,Cornell University Technical Report TR 75-260 and Proc. Eighth ACM Symp. Theory of Computing (1976); 30–40.

  6. N. Jones andA. Selman, Turing machines and the spectra of first-order formulas,J. Symbolic Logic 39 (1974), 139–150.

    Google Scholar 

  7. R. Lander, On the structure of polynomial time reducibility,J. Assoc. Comput. Mach 22 (1975), 155–171.

    Google Scholar 

  8. R. Lander, N. Lynch, andA. Selman, A comparison of polynomial time reducibilities,Theoretical Computer Sci. 1 (1975), 103–123.

    Google Scholar 

  9. W. Savitch, Relationships between nondeterministic and deterministic tape complexities,J. Computer System Sci. 4 (1970), 177–192.

    Google Scholar 

  10. W. Savitch, A note on multihead and context-sensitive languages,Acta Informatica 2 (1973), 249–252.

    Google Scholar 

  11. S. Sahni, Computationally related problems,SIAM J. Computing 3 (1974), 262–279.

    Google Scholar 

  12. S. Sahni, andT. Gonzaiez,P-complete approximation problems,J. Assoc. Comput. Mach. 23 (1976), 555–565.

    Google Scholar 

  13. C. Wrathall,Subrecursive Predicates and Automata, Ph.D. Dissertation, Harvard University, 1975.

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science Program, University of California, 93106, Santa Barbara, California, USA

    Ronald V. Book

  2. Department of System Science, University of California, 90024, Los Angeles, California, USA

    Celia Wrathall

  3. Department of Computer Science, Iowa State University, 50011, Ames, Iowa, USA

    Alan L. Selman

  4. Department of Computer Science, Yale University, 06520, New Haven, Connecticut, USA

    David Dobkin

Authors
  1. Ronald V. Book
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Celia Wrathall
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alan L. Selman
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. David Dobkin
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported in part by the National Science Foundation under Grants MCS76-05744 and MCS77-11360.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Book, R.V., Wrathall, C., Selman, A.L. et al. Inclusion complete tally languages and the Hartmanis-Berman conjecture. Math. Systems Theory 11, 1–8 (1977). https://doi.org/10.1007/BF01768464

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation