Relationship between density and deterministic complexity of MP-complete languages

Piotr Berman

doi:10.1007/3-540-08860-1_6

Relationship between density and deterministic complexity of MP-complete languages

Piotr Berman

Eberly College of Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

50 Scopus citations

Abstract

Let Σ be an arbitrary alphabet. denotes ɛ∪Σ∪..∪Σⁿ. We say that a function t, t: is f-sparse iff card for every natural n. The main theorem of this paper establishes that if CLIQUE has some f-sparse translation into another set, which is calculable by a deterministic Turing machine in time bounded by f, then all the sets belonging to NP are calculable in time bounded by a function polynomially related to f. The proof is constructive and shows the way of constructing a proper algorithm. The simplest and most significant corollary says that if there is an NP-complete language over a single letter alphabet, then P=NP.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 5th Colloquium
Editors	Corrado Bohm, Giorgio Ausiello
Publisher	Springer Verlag
Pages	63-71
Number of pages	9
ISBN (Print)	9783540088608
DOIs	https://doi.org/10.1007/3-540-08860-1_6
State	Published - 1978
Event	5th International Colloquium on Automata, Languages and Programming, ICALP 1978 - Udine, Italy Duration: Jul 17 1978 → Jul 21 1978

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	62 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	5th International Colloquium on Automata, Languages and Programming, ICALP 1978
Country/Territory	Italy
City	Udine
Period	7/17/78 → 7/21/78

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-08860-1_6

Cite this

Berman, P. (1978). Relationship between density and deterministic complexity of MP-complete languages. In C. Bohm, & G. Ausiello (Eds.), Automata, Languages and Programming - 5th Colloquium (pp. 63-71). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 62 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-08860-1_6

@inproceedings{1b5459306df649fb9f13a7ae21214a46,

title = "Relationship between density and deterministic complexity of MP-complete languages",

abstract = "Let Σ be an arbitrary alphabet. denotes ɛ∪Σ∪..∪Σn. We say that a function t, t: is f-sparse iff card for every natural n. The main theorem of this paper establishes that if CLIQUE has some f-sparse translation into another set, which is calculable by a deterministic Turing machine in time bounded by f, then all the sets belonging to NP are calculable in time bounded by a function polynomially related to f. The proof is constructive and shows the way of constructing a proper algorithm. The simplest and most significant corollary says that if there is an NP-complete language over a single letter alphabet, then P=NP.",

author = "Piotr Berman",

note = "Publisher Copyright: {\textcopyright} 1978, Springer-Verlag. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.; 5th International Colloquium on Automata, Languages and Programming, ICALP 1978 ; Conference date: 17-07-1978 Through 21-07-1978",

year = "1978",

doi = "10.1007/3-540-08860-1_6",

language = "English (US)",

isbn = "9783540088608",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "63--71",

editor = "Corrado Bohm and Giorgio Ausiello",

booktitle = "Automata, Languages and Programming - 5th Colloquium",

address = "Germany",

}

Berman, P 1978, Relationship between density and deterministic complexity of MP-complete languages. in C Bohm & G Ausiello (eds), Automata, Languages and Programming - 5th Colloquium. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 62 LNCS, Springer Verlag, pp. 63-71, 5th International Colloquium on Automata, Languages and Programming, ICALP 1978, Udine, Italy, 7/17/78. https://doi.org/10.1007/3-540-08860-1_6

Relationship between density and deterministic complexity of MP-complete languages. / Berman, Piotr.
Automata, Languages and Programming - 5th Colloquium. ed. / Corrado Bohm; Giorgio Ausiello. Springer Verlag, 1978. p. 63-71 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 62 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Relationship between density and deterministic complexity of MP-complete languages

AU - Berman, Piotr

PY - 1978

Y1 - 1978

N2 - Let Σ be an arbitrary alphabet. denotes ɛ∪Σ∪..∪Σn. We say that a function t, t: is f-sparse iff card for every natural n. The main theorem of this paper establishes that if CLIQUE has some f-sparse translation into another set, which is calculable by a deterministic Turing machine in time bounded by f, then all the sets belonging to NP are calculable in time bounded by a function polynomially related to f. The proof is constructive and shows the way of constructing a proper algorithm. The simplest and most significant corollary says that if there is an NP-complete language over a single letter alphabet, then P=NP.

AB - Let Σ be an arbitrary alphabet. denotes ɛ∪Σ∪..∪Σn. We say that a function t, t: is f-sparse iff card for every natural n. The main theorem of this paper establishes that if CLIQUE has some f-sparse translation into another set, which is calculable by a deterministic Turing machine in time bounded by f, then all the sets belonging to NP are calculable in time bounded by a function polynomially related to f. The proof is constructive and shows the way of constructing a proper algorithm. The simplest and most significant corollary says that if there is an NP-complete language over a single letter alphabet, then P=NP.

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

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

U2 - 10.1007/3-540-08860-1_6

DO - 10.1007/3-540-08860-1_6

M3 - Conference contribution

AN - SCOPUS:85034603266

SN - 9783540088608

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 63

EP - 71

BT - Automata, Languages and Programming - 5th Colloquium

A2 - Bohm, Corrado

A2 - Ausiello, Giorgio

PB - Springer Verlag

T2 - 5th International Colloquium on Automata, Languages and Programming, ICALP 1978

Y2 - 17 July 1978 through 21 July 1978

ER -

Berman P. Relationship between density and deterministic complexity of MP-complete languages. In Bohm C, Ausiello G, editors, Automata, Languages and Programming - 5th Colloquium. Springer Verlag. 1978. p. 63-71. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-08860-1_6

Relationship between density and deterministic complexity of MP-complete languages

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this