@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",
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",
}