A time lower bound for satisfiability

Dieter Van Melkebeek, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingChapter

4 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 a3 < 1 + a/(d + 1). The same bounds apply to almost all natural NP-complete problems known.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsJosep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella
PublisherSpringer Verlag
Pages971-982
Number of pages12
ISBN (Print)3540228497
DOIs
StatePublished - 2004
Externally publishedYes

Publication series

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

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A time lower bound for satisfiability'. Together they form a unique fingerprint.

  • 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