Storage requirements for deterministic polynomialtime recognizable languages

Stephen Cook, Ravi Sethi

Research output: Contribution to journalArticlepeer-review

58 Scopus citations


An intriguing question is whether (log n)2 space is enough to recognize the class {A figure is presented} of languages recognizable in deterministic polynomial time. This question has earlier been narrowed down to the storage required to recognize a particular language called SP. SP is clearly in {A figure is presented} and it has been shown that if SP has tape complexity (log n)k, then every member of {A figure is presented} has tape complexity (log n)k. This paper presents further evidence in support of the conjecture that SP cannot be recognized using storage (log n)k for any k. We have no techniques at present for proving such a statement for Turing machines in general; we prove the result for a suitably restricted device.

Original languageEnglish (US)
Pages (from-to)25-37
Number of pages13
JournalJournal of Computer and System Sciences
Issue number1
StatePublished - Aug 1976

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Storage requirements for deterministic polynomialtime recognizable languages'. Together they form a unique fingerprint.

Cite this