Inclusion complete tally languages and the Hartmanis-Berman conjecture

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

doi:10.1007/BF01768464

Inclusion complete tally languages and the Hartmanis-Berman conjecture

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

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	1-8
Number of pages	8
Journal	Mathematical Systems Theory
Volume	11
Issue number	1
DOIs	https://doi.org/10.1007/BF01768464
State	Published - Dec 1977

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics

Access to Document

10.1007/BF01768464

Cite this

@article{eee58677ddad450983df9b9c1c776ecb,

title = "Inclusion complete tally languages and the Hartmanis-Berman conjecture",

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.",

author = "Book, {Ronald V.} and Celia Wrathall and Selman, {Alan L.} and David Dobkin",

year = "1977",

month = dec,

doi = "10.1007/BF01768464",

language = "English (US)",

volume = "11",

pages = "1--8",

journal = "Mathematical Systems Theory",

issn = "0025-5661",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Inclusion complete tally languages and the Hartmanis-Berman conjecture

AU - Book, Ronald V.

AU - Wrathall, Celia

AU - Selman, Alan L.

AU - Dobkin, David

PY - 1977/12

Y1 - 1977/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0039349991&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039349991&partnerID=8YFLogxK

U2 - 10.1007/BF01768464

DO - 10.1007/BF01768464

M3 - Article

AN - SCOPUS:0039349991

SN - 0025-5661

VL - 11

SP - 1

EP - 8

JO - Mathematical Systems Theory

JF - Mathematical Systems Theory

IS - 1

ER -

Inclusion complete tally languages and the Hartmanis-Berman conjecture

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this