__
TR08-076 | 17th June 2008 00:00
__

#### Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas

**Abstract:**
We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable machine models, including multitape Turing machines, random access Turing machines, tree computers, and logarithmic-cost RAMs. By a simple diagonalization, it follows that the succinct QBF problem requires superlinear time on those models. To our knowledge this is the first known instance of a non-linear time lower bound (with no space restriction) for solving a natural linear space problem on a variety of computational models.