@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: dieter@cs.wisc.edu (D. van Melkebeek), ran.raz@weizmann.ac.il (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",

}