«Abstract We prove a model-independent non-linear time lower bound for a slight generalization of the quan- tiﬁed Boolean formula problem (QBF). In ...»
Non-Linear Time Lower Bound for (Succinct) Quantiﬁed Boolean
Carnegie Mellon University
We prove a model-independent non-linear time lower bound for a slight generalization of the quan-
tiﬁed 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 encod-
ing. 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 diagonal- ization, it follows that the succinct QBF problem requires superlinear time on those models. To our knowledge this is the ﬁrst 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.
∗ Email: email@example.com.
1 Introduction While our knowledge of time eﬃcient algorithms has grown to a good level of sophistication, when it comes to proving time lower bounds we still have a long road ahead of us. It seems that we are far from set- tling frontier separation problems like P = PSPACE, although some modest progress has been made on LOGSPACE = NP in the form of time-space tradeoﬀs for satisﬁability (see e.g. [vM07, Wil07] for recent overviews of this line of work). However, these time-space tradeoﬀ lower bounds critically rely on tiny space bounds. Even the task of proving non-linear time lower bounds for natural problems within PSPACE has become a surprisingly formidable challenge. Since the seminal result of Paul-Pippenger-Szemeredi-Trotter that DTIME[n] = NTIME[n] for multitape Turing machines [PPST83], not much progress has been made on proving non-linear time lower bounds for NP problems. Progress has also stalled on lower bounds for PSPACE problems as well. For more details, see the survey by Regan [Reg95] (which is still up-to-date today).
In this paper we establish a non-linear time lower bound on a variant of the canonical PSPACE-complete problem: that of determining if an arbitrary quantiﬁed Boolean formula is true (abbreviated as QBF). Our result holds for a variety of computational models, both sequential-access and random-access. The proof interleaves several diagonalization-based components from prior work, and it yields new insight into how we can prove lower bounds on natural problems by bootstrapping from lower bounds for artiﬁcial problems (for example, those arising from a time hierarchy theorem). Such results are interesting since lower bounds for artiﬁcially constructed problems are plentiful, while bounds for natural well-studied problems are rare.
Here we give a reduction-based approach to lower boundsfor QBF, by showing that if we choose a natural, polynomially succinct encoding for formulas, then we can reduce arbitrary languages in alternating time t(n) to quantiﬁed Boolean formulas that use O(t(n)) bits to describe. This reduction, coupled with the fact that deterministic algorithms can be simulated asymptotically faster with alternating algorithms, yields a non-linear lower bound for solving these succinct QBFs. It is important to note that such a reduction is impossible to achieve with QBFs encoded in the traditional way (in preﬁx-normal form with a CNF predicate), since in that case the QBF instances of length n can be actually solved in alternating O(n/ log n) time by machines having random access to the input.1 Thus the existence of such a reduction would imply ATIME[t(n)] ⊆ ATIME[t(n)/ log t(n)], an absurdity.
Why is this result new? It has been known for many years that deterministic algorithms can be simulated with faster alternating algorithms [PPR80, DT85, Mak94, Mak97]; in fact, multitape Turing machines can be simulated faster by alternating multitape Turing machines that take only a constant number of alternations [PPST83]. Clearly these results show that there is some language in alternating time O(n) that cannot be solved in deterministic time O(n). However, one cannot conclude a non-linear time lower bound for QBF (even our succinct QBF problem) because of the overheads in known reductions: the best known reductions from arbitrary alternating time t(n) languages to quantiﬁed Boolean formulas result in QBFs of at least Ω(t(n) log2 t(n)) size [Sch78, Coo88, Rob91]. (Also, one cannot conclude lower bounds for QBF from results like DTIME[t(n)] ⊆ SPACE[t/ log t] [HPV77], as the best known reduction from SPACE[n] to QBF via Savitch’s theorem [Sav70] outputs a formula of Θ(n2 log n) bits [SM73].) In this paper, we eliminate the log2 t blowup in these reductions by choosing a good encoding and exploiting the power of alternation. The result is that we provide a time lower bound for a natural variant of QBF that allows for groups of log n variables to “address” one of the n variables. (For more details, see the next section.) 1 To see this, ﬁrst note that any formula with N variable occurrences requires Ω(N log N ) bits to write down, so a QBF of length n can have only O(n/ log n) variables under the normal encoding. Secondly, note that a single clause can be (universally) chosen in O(log n) time, and a single literal of a clause can be (existentially) chosen in O(log n) time. An alternating algorithm for QBF could then (in O(n/ log n) time) guess bits for all the relevant variables in its quantiﬁer preﬁx, universally guess a clause, existentially guess a literal (to be true), existentially guess where the corresponding variable is located in the quantiﬁer preﬁx, then check all its guesses.
1 2 Preliminaries We use the abbreviations: TM for “Turing machine”, ATM for “alternating Turing machine”, RAM for “random access machine”, and ARAM for “alternating random access machine.” In this paper, all our TMs are allowed to have access to multiple input tapes. We refer to a one-tape TM as a Turing machine that is allowed random access and two-way access to multiple read-only input tapes, and one read-write tape that is two-way sequentially accessed. The random accesses can be up to polylogarithmic cost. A very similar model has been studied before in context of time lower bounds [vMR05].
Related Work. In the past, there have been several demonstrations of time lower bounds for natural problems with no space restriction. Adachi et al. [AIK84] showed that a problem called the cat and kmouse game requires at least nΩ(k) time (inﬁnitely often) to solve on a multitape TM, using a reduction from DTIME[nk ] to the game. Grandjean [Gra88, Gra90] applied the result that DTIME[n] = NTIME[n] for multitape TMs [PPST83] to prove that a satisﬁability problem over the natural numbers and the NPcomplete problem Reduction of Incompletely Speciﬁed Automata ([GJ79], Problem AL7) both require nonlinear time on a multitape TM. While the above work also uses reductions to obtain their results, our work diﬀers signiﬁcantly in both techniques and implications: we utilize alternations in a novel way to keep our reduction’s runtime low, and as a result, our reduction works for many more computational models than multitape TMs.
Our Encoding of QBFs. Let us describe one encoding of Boolean formulas that suﬃces for our results.
We restrict ourselves to QBFs in prenex normal form, where the underlying Boolean formula F is written in conjunctive normal form, for example (∃ x1 )(∀ x2 ) · · · (∃ xn )F.
Here our atoms shall be the literals (variables xi and their negations ¬xi ) as well as the address functions X(xj1,..., xj⌈log n⌉ ), where j1,..., j⌈log n⌉ ∈ [n]. For binary values vjk, the meaning of X(vj1,..., vj⌈log n⌉ ) is the variable xi, where the bit string vj1 · · · vj⌈log n⌉ represents the binary encoding of i. The X-function allows us to refer to a range of variables without actually writing down all of their indices. For example, the
following is a QBF in our encoding:
(∃x1 )(∀x2 )(∃x3 )(∃x4 )[X(x2, x1 ) ∨ X(x4, x3 )].
The formula is true, since by setting x1 = 1, x3 = 1, and x4 = 1, X(0, 1) = x1 and X(1, 1) = x4 are both true.
It is important to observe that formulas encoded with the X-function are only “polynomially succinct” representations, and not exponentially succinct: any instance of the X-function can be replaced by a collection of O(n) clauses that encode a circuit for the storage access function SAn (a0,..., ak−1, x0,..., x2k −1 ) = xa. We remark that our use of X could be exchanged for other encoding mechanisms as well. For example, Gurevich and Shelah [GS89] have deﬁned generalized Boolean formulas, which also use a form of variable addressing. Quantiﬁed versions of generalized Boolean formulas would also be amenable to our reduction.
For a QBF in prenex normal form, we use O(n) bits to describe the variable preﬁx, where the ith bit describes the quantiﬁcation of variable xi. For a formula F with ℓ occurrences of literals (as atoms) and at most O(ℓ/ log n) occurrences of the X-function, we use O(n + ℓ log n) bits to describe F, taking O(1) bits to write ORs and ANDs, O(log2 n) bits to write down an instance of the X-function (as it takes O(log n) literals as input), and O(log n) bits to write variables and their negations.
The Models Studied. We assume the reader is familiar with the multitape Turing machine model. This
work also discusses a few more models that may require a brief recollection:
• Logarithmic-Cost RAM: Here we have a random access machine with the usual addition, load/store, and simple branching instructions. The memory storage is a collection of registers, each holding an integer. Any operations on a register holding integer i take Θ(log i) steps, so e.g. a random access to a location among s registers takes O(log s) steps.
• Random Access TM: Same functionality as the multitape TM, except that accesses to each tape are performed by writing bits to a special sequential “index tape” of O(log t) length, after which the tape head jumps to the location speciﬁed by the index tape content.
• Tree Computer: The auxiliary tapes of a multitape TM are replaced with binary trees. Each node of the tree contains a single symbol (like a tape cell), and the ﬁnite control’s directions specify whether to move to the parent, left child, or right child of the current node.
• Multi-dimensional TM: The auxiliary tapes are replaced by k-dimensional cubes, for a ﬁxed constant k. Finite control directions specify which of 2k directions to move to, from the current cell of the cube.
We assume all the above models receive their input on an initial tape of n separate cells (so that every non-trivial problem requires at least linear time to solve). We remark that, on any of the alternating computational models that we study, our succinct QBFs can be solved in linear time.
Three prior results are utilized in our reduction. The ﬁrst says that we can speed up the simulation of a one-tape TM by introducing alternations.
Theorem 2.1 (Maass-Schorr [MS87], Van Melkebeek-Raz [vMR05]) Every deterministic linear time one-tape TM M can be simulated by a Σ2 random access TM that runs in O(n2/3 log2 n) time.
In particular, the Σ2 computation works by ﬁrst existentially guessing O(n2/3 log n) bits on an auxiliary tape T, universally writing O(log n) bits to T, then executing a deterministic O(n2/3 log2 n) time computation on a one-tape TM that takes the original input tapes of M and T as its own (random-access, read-only) input tapes.
Proof. (Sketch) We combine a crossing sequence argument with a result that shows how to speed up small space computations with an alternating machine. Let M ﬁt the conditions of the theorem statement and let x be an input. Let CS(x) be the set of crossing sequences for M (x) on its read-write sequential tape.
We associate each sequence with a cell of the tape. Notice that each element of a crossing sequence for a particular cell is of O(log n) size (by storing the current position of the input heads in each element).
For every i = 1,..., n1/3, deﬁne CS(x, i) to be the subset of sequences from CS(x) that range over the tape cells numbered i + k · n1/3, for k = 0, 1,..., n2/3 − 1. Observe that the union of all CS(x, i) is exactly CS(x), and that CS(x, i) ∩ CS(x, j) = ∅ for i = j. Since the total sum of the lengths of all crossing sequences for M (x) is O(n), there is a j where the total length (in bits) of all crossing sequences in CS(x, j) is at most O(n2/3 log n). If we existentially guess CS(x, j) upfront (on a tape T ), then our computation of M (x) reduces to an O(n log n) time and O(n1/3 log n) space one-tape TM computation which checks that the computation between the crossing sequences of CS(x, j) is valid and accepting.
We have now a nondeterministic computation that guesses O(n2/3 log n) bits, then runs an O(n log n) time and O(n1/3 log n) space one-tape TM computation. To obtain a Σ2 random access TM of the desired form, we use a fast simulation of space-bounded computation that dates back to Kannan [Kan84]. Start by existentially guessing a list of O(n1/3 ) conﬁgurations of the one-tape TM on input x. Such a guess can be written down on the tape T using O(n2/3 log n) bits. We then universally choose a pair of adjacent conﬁgurations on the list, by writing O(log n) bits on T. Finally, we move the tape head to the guessed pair, and verify that from the ﬁrst conﬁguration in the pair, the second conﬁguration can be reached within
Theorem 2.2 (Cook [Coo88]) Let M be a t(n) time bounded multitape Turing machine.
For each input x there is a CNF F having O(t(n) log t(n)) literals such that F is satisﬁable if and only if M (x) accepts.
Moreover, the CNF can be constructed in O(t(n) log2 t(n)) time on a multitape TM.
Cook actually proves the result for nondeterministic Turing machines, pointing out that Pippenger and Fischer’s O(t(n) log t(n))-size circuits for time t(n) machines [PF79] yield the result easily. The idea behind the construction of the circuits is to take an arbitrary time t(n) Turing machine and make it oblivious to its inputs: that is, the tape head movements of the Turing machine on an input x depends only on |x|, the input length. The oblivious simulation yields a Turing machine that runs in O(t(n) log t(n)) time.