Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-076 | 17th June 2008 00:00

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


Authors: Ryan Williams
Publication: 28th August 2008 20:07
Downloads: 1443


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.

ISSN 1433-8092 | Imprint