A time lower bound for satisfiability

Dieter Van Melkebeek; Ran Raz

doi:10.1007/978-3-540-27836-8_81

A time lower bound for satisfiability

Dieter Van Melkebeek, Ran Raz

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

8 Scopus citations

Abstract

We show that a deterministic Turing machine with one d-dimensional work tape and random access to the input cannot solve satisfiability in time n ^a for a < √(d + 2)/(d + 1). For conondeterministic machines, we obtain a similar lower bound for any a such that a³ < 1 + a/(d + 1). The same bounds apply to almost all natural NP-complete problems known.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Josep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella
Publisher	Springer Verlag
Pages	971-982
Number of pages	12
ISBN (Print)	3540228497
DOIs	https://doi.org/10.1007/978-3-540-27836-8_81
State	Published - 2004
Externally published	Yes

Publication series

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

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-27836-8_81

Cite this

Van Melkebeek, D., & Raz, R. (2004). A time lower bound for satisfiability. In J. Díaz, J. Karhumäki, A. Lepistö, & D. Sannella (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 971-982). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3142). Springer Verlag. https://doi.org/10.1007/978-3-540-27836-8_81

Van Melkebeek, Dieter ; Raz, Ran. / A time lower bound for satisfiability. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Josep Díaz ; Juhani Karhumäki ; Arto Lepistö ; Donald Sannella. Springer Verlag, 2004. pp. 971-982 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{fbc26c1e6f80401386db5fe293944cb0,

title = "A time lower bound for satisfiability",

abstract = "We show that a deterministic Turing machine with one d-dimensional work tape and random access to the input cannot solve satisfiability in time n a for a < √(d + 2)/(d + 1). For conondeterministic machines, we obtain a similar lower bound for any a such that a3 < 1 + a/(d + 1). The same bounds apply to almost all natural NP-complete problems known.",

author = "{Van Melkebeek}, Dieter and Ran Raz",

note = "Funding Information: A preliminary version of this paper appeared in the Proceedings of the 31st International Colloquium on Automata, Languages and Programming. ∗Corresponding author. E-mail addresses: [email protected] (D. van Melkebeek), [email protected] (R. Raz) URLs: http://www.cs.wisc.edu/∼dieter (D. van Melkebeek), http://www.wisdom.weizmann.ac.il/∼ranraz (R. Raz). 1Partially supported by NSF Career award CCR-0133693.",

year = "2004",

doi = "10.1007/978-3-540-27836-8_81",

language = "English (US)",

isbn = "3540228497",

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

publisher = "Springer Verlag",

pages = "971--982",

editor = "Josep D{\'i}az and Juhani Karhum{\"a}ki and Arto Lepist{\"o} and Donald Sannella",

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

address = "Germany",

}

Van Melkebeek, D & Raz, R 2004, A time lower bound for satisfiability. in J Díaz, J Karhumäki, A Lepistö & D Sannella (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3142, Springer Verlag, pp. 971-982. https://doi.org/10.1007/978-3-540-27836-8_81

A time lower bound for satisfiability. / Van Melkebeek, Dieter; Raz, Ran.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Josep Díaz; Juhani Karhumäki; Arto Lepistö; Donald Sannella. Springer Verlag, 2004. p. 971-982 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3142).

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

TY - CHAP

T1 - A time lower bound for satisfiability

AU - Van Melkebeek, Dieter

AU - Raz, Ran

N1 - Funding Information: A preliminary version of this paper appeared in the Proceedings of the 31st International Colloquium on Automata, Languages and Programming. ∗Corresponding author. E-mail addresses: [email protected] (D. van Melkebeek), [email protected] (R. Raz) URLs: http://www.cs.wisc.edu/∼dieter (D. van Melkebeek), http://www.wisdom.weizmann.ac.il/∼ranraz (R. Raz). 1Partially supported by NSF Career award CCR-0133693.

PY - 2004

Y1 - 2004

N2 - We show that a deterministic Turing machine with one d-dimensional work tape and random access to the input cannot solve satisfiability in time n a for a < √(d + 2)/(d + 1). For conondeterministic machines, we obtain a similar lower bound for any a such that a3 < 1 + a/(d + 1). The same bounds apply to almost all natural NP-complete problems known.

AB - We show that a deterministic Turing machine with one d-dimensional work tape and random access to the input cannot solve satisfiability in time n a for a < √(d + 2)/(d + 1). For conondeterministic machines, we obtain a similar lower bound for any a such that a3 < 1 + a/(d + 1). The same bounds apply to almost all natural NP-complete problems known.

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

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

U2 - 10.1007/978-3-540-27836-8_81

DO - 10.1007/978-3-540-27836-8_81

M3 - Chapter

AN - SCOPUS:35048855636

SN - 3540228497

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

SP - 971

EP - 982

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

A2 - Díaz, Josep

A2 - Karhumäki, Juhani

A2 - Lepistö, Arto

A2 - Sannella, Donald

PB - Springer Verlag

ER -

Van Melkebeek D, Raz R. A time lower bound for satisfiability. In Díaz J, Karhumäki J, Lepistö A, Sannella D, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 971-982. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-27836-8_81

A time lower bound for satisfiability

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this