Speaker: Dieter van Melkebeek
Affiliation: Institute for Advanced Study
Date: 3/29/01
Time and Location: 4:15 PM, B11 Kimball Hall
Title: Time-Space Tradeoffs for Satisfiability
Abstract: 

Satisfiability is the problem of deciding whether a given propositional formula has a satisfying assignment. It is the seminal NP-complete problem and is of major practical importance. Although we expect satisfiability to take exponential time in the worst case, we do not know how to prove that no linear-time algorithm exists on a general-purpose random-access machine. The same situation holds for Boolean circuits deciding satisfiability.

In recent years we have seen a new approach to establish superlinear time lower bounds for machines that only use a small amount of space. We will survey the underlying ideas and present the strongest result of this type so far: Satisfiability cannot be solved on general-purpose random-access machines running in 
n ^ {1.618} time and subpolynomial space. In general, for any constant c less than the golden ratio, we prove that satisfiability cannot be solved in n^c time and n^d space for some positive constant d depending on c.

We obtain these results by establishing time-space tradeoffs for nondeterministic linear time. The same techniques yield new lower bounds on conondeterministic versus nondeterministic computation, as well as on circuits deciding satisfiability.

Part of this work was done jointly with Lance Fortnow.