Inclusion complete tally languages and the Hartmanis-Berman conjecture

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

Research output: Contribution to journalArticle

15 Scopus citations

Abstract

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
Volume11
Issue number1
DOIs
StatePublished - Dec 1 1977
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics

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

  • Cite this