Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas
Ryan Williams · 2008
Abstract. We give a reduction from arbitrary languages in alternating time t(n) to quantified Boolean formulas (QBF) describable in O(t(n)) bits. The reduction works for a reasonable succinct encoding of Boolean formulas and for several reasonable machine models, including multitape Turing machines and logarithmic-cost RAMs. By a simple diagonalization, it follows that our 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.