A time lower bound for satisfiability

Dieter Van Melkebeek, Ran Raz

Research output: Contribution to journalArticle

5 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 languageEnglish (US)
Pages (from-to)311-320
Number of pages10
JournalTheoretical Computer Science
Volume348
Issue number2-3 SPEC. ISS.
DOIs
StatePublished - Dec 8 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Computational complexity
  • Lower bounds
  • Satisfiability

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

  • Cite this