𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Time–Space Tradeoffs for Satisfiability

✍ Scribed by Lance Fortnow

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
180 KB
Volume
60
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We give the first nontrivial model-independent time space tradeoffs for satisfiability. Namely, we show that SAT cannot be solved in n 1+o(1) time and n 1&= space for any =>0 general random-access nondeterministic Turing machines. In particular, SAT cannot be solved deterministically by a Turing machine using quasilinear time andn space. We also give lower bounds for log-space uniform NC 1 circuits and branching programs. Our proof uses two basic ideas. First we show that if SAT can be solved nondeterministically with a small amount of time then we can collapse a nonconstant number of levels of the polynomial-time hierarchy. We combine this work with a result of Nepomnjas c i@$ that shows that a nondeterministic computation of superlinear time and sublinear space can be simulated in alternating linear time. A simple diagonalization yields our main result. We discuss how these bounds lead to a new approach to separating the complexity classes NL and NP. We give some possibilities and limitations of this approach.

📜 SIMILAR VOLUMES

Time–Space Tradeoffs for Branching Progr
Time–Space Tradeoffs for Branching Programs
✍ Paul Beame; T.S. Jayram; Michael Saks 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 265 KB

We obtain the first non-trivial time-space tradeoff lower bound for functions f: {0, 1} n Q {0, 1} on general branching programs by exhibiting a Boolean function f that requires exponential size to be computed by any branching program of length (1+e) n, for some constant e > 0. We also give the firs

Topological parameters for time-space tr
Topological parameters for time-space tradeoff
✍ Rina Dechter; Yousri El Fattah 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 463 KB

In this paper we propose a family of algorithms combining tree-clustering with conditioning that trade space for time. Such algorithms are useful for reasoning in probabilistic and deterministic networks as well as for accomplishing optimization tasks. By analyzing the problem structure, the user ca

Time–Space Tradeoffs for SAT on Nonunifo
Time–Space Tradeoffs for SAT on Nonuniform Machines
✍ Iannis Tourlakis 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 176 KB

are generalized and combined with an argument for diagonalizing over machines taking n bits of advice on inputs of length n to obtain the first nontrivial time-space lower bounds for SAT on nonuniform machines. In particular, we show that for any a < `2 and any e > 0, SAT cannot be computed by a ra

Time-Space Tradeoffs in Algebraic Comple
Time-Space Tradeoffs in Algebraic Complexity Theory
✍ M. Aldaz; J. Heintz; G. Matera; J.L. Montaña; L.M. Pardo 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 294 KB

We exhibit a new method for showing lower bounds for time-space tradeoffs of polynomial evaluation procedures given by straight-line programs. From the tradeoff results obtained by this method we deduce lower space bounds for polynomial evaluation procedures running in optimal nonscalar time. Time,

Optimal Time–Space Tradeoff for Shared M
Optimal Time–Space Tradeoff for Shared Memory Leader Election
✍ Yehuda Afek; Gideon Stupp 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 283 KB

Though it is common practice to treat synchronization primitives for multiprocessors as abstract data types, they are in reality machine instructions on registers. A crucial theoretical question with practical implications is the relationship between the size of the register and its computational po