A time lower bound for satisfiability

Dieter Van Melkebeek; Ran Raz

doi:10.1016/j.tcs.2005.09.020

A time lower bound for satisfiability

Dieter Van Melkebeek, Ran Raz

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

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

Original language	English (US)
Pages (from-to)	311-320
Number of pages	10
Journal	Theoretical Computer Science
Volume	348
Issue number	2-3 SPEC. ISS.
DOIs	https://doi.org/10.1016/j.tcs.2005.09.020
State	Published - Dec 8 2005
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Keywords

Computational complexity
Lower bounds
Satisfiability

Access to Document

10.1016/j.tcs.2005.09.020

Cite this

@article{9343d15b26354481a093f22afc403e82,

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

keywords = "Computational complexity, Lower bounds, Satisfiability",

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 = "2005",

month = dec,

day = "8",

doi = "10.1016/j.tcs.2005.09.020",

language = "English (US)",

volume = "348",

pages = "311--320",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "2-3 SPEC. ISS.",

}

TY - JOUR

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 - 2005/12/8

Y1 - 2005/12/8

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

KW - Computational complexity

KW - Lower bounds

KW - Satisfiability

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

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

U2 - 10.1016/j.tcs.2005.09.020

DO - 10.1016/j.tcs.2005.09.020

M3 - Article

AN - SCOPUS:33644557714

SN - 0304-3975

VL - 348

SP - 311

EP - 320

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2-3 SPEC. ISS.

ER -

A time lower bound for satisfiability

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this