Inclusion complete tally languages and the Hartmanis-Berman conjecture

Ronald V. Book, Celia Wrathall, Alan L. Selman, David Dobkin

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


Stimulated by the work of Hartmanis and Berman [5], we study the question of the existence of a tally language L in NP such that L is in P if and only if P = 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.

Original languageEnglish (US)
Pages (from-to)1-8
Number of pages8
JournalMathematical Systems Theory
Issue number1
StatePublished - Dec 1977

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Inclusion complete tally languages and the Hartmanis-Berman conjecture'. Together they form a unique fingerprint.

Cite this