FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

«Abstract We prove a model-independent non-linear time lower bound for a slight generalization of the quan- tified Boolean formula problem (QBF). In ...»

-- [ Page 1 ] --

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


Ryan Williams∗

Carnegie Mellon University


We prove a model-independent non-linear time lower bound for a slight generalization of the quan-

tified 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 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.

∗ Email: ryanw@cs.cmu.edu.

1 Introduction While our knowledge of time efficient 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 tradeoffs for satisfiability (see e.g. [vM07, Wil07] for recent overviews of this line of work). However, these time-space tradeoff 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 quantified 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 artificial problems (for example, those arising from a time hierarchy theorem). Such results are interesting since lower bounds for artificially 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 quantified 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 prefix-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 quantified 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, first 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 quantifier prefix, universally guess a clause, existentially guess a literal (to be true), existentially guess where the corresponding variable is located in the quantifier prefix, 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 (infinitely 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 satisfiability problem over the natural numbers and the NPcomplete problem Reduction of Incompletely Specified 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 differs significantly 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 suffices 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 defined generalized Boolean formulas, which also use a form of variable addressing. Quantified 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 prefix, where the ith bit describes the quantification 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 specified 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 finite 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 fixed 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 first 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 first 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 fit 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, define 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 ) configurations 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 configurations 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 first configuration in the pair, the second configuration 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 satisfiable 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.

Pages:   || 2 | 3 |

Similar works:

«FOR IMMEDIATE RELEASE Contact: Mark Saunders Dec. 30, 2015 202.268.6524 mark.r.saunders@usps.gov usps.com/news Postal Service Previews 2016 Stamps Star Trek, NASA’s New Horizons and Shirley Temple are among Topics Highlighted High-resolution images of the stamps are available for media use only by emailing mark.r.saunders@usps.gov WASHINGTON — The Postal Service is providing a preview of its 2016 stamp program that is sure to attract the interest of fans of Sarah Vaughan, Star Trek,...»

«Res High Educ (2009) 50:546–569 DOI 10.1007/s11162-009-9134-y The Influence of Institutional Retention Climates on Student Persistence to Degree Completion: A Multilevel Approach Leticia Oseguera Æ Byung Shik Rhee Received: 28 March 2008 / Published online: 3 April 2009 Ó The Author(s) 2009. This article is published with open access at Springerlink.com Abstract Using multi-institutional data from the Cooperative Institutional Research Program’s (CIRP) annual survey of entering freshmen,...»

«Laylla Rkiouak WANA institute May 2015 Laylla Rkiouak WANA institute May 2015 A regional ethics-based sustainable development model for the West Asia-North Africa region Laylla Rkiouak, Research fellow, WANA institute (corresponding author) lrkiouak@gmail.com Majlis el Hassan, Amman, Jordan Abstract This study proposes that viable transition to sustainable development requires a new, et hically-centered, sustainable development model. Moreover, the development of a model inspired by Islamic...»

«НАУЧНИ ТРУДОВЕ НА РУСЕНСКИЯ УНИВЕРСИТЕТ 2014, том 53, серия 1.1 Biogas production of phytoremediation plants contaminated with cadmium Martin Šotnar, Jan Mareček, Pavel Máchal, Tomáš Koutný, Milan Geršl, Eva Krčálová, Maroš Korenko Abstract: This work is about biogas production of phytoremediation plants contaminated with cadmium. As the phytoremediation plant was chosen maize (Zea mays). For growing of corn sown ( HYBRID ): CE 220 was used...»

«PROFILE Nobuyasu ABE is Vice-Chairman, Japan Atomic Energy Commission (April 2014). Former United Nations Under-Secretary-General for Disarmament Affairs (2003-06) and Director-General for Arms Control and Science Affairs (1997-99) of the Ministry of Foreign Affairs of Japan. Director of the Center for the Promotion of Disarmament and Non-Proliferation at the Japan Institute of International Affairs (2008-14). Ambassador of Japan to the IAEA and other international organizations in Vienna...»

«Crop Profile for Watermelons in Missouri Prepared: March, 2000 General Production Information (Citrullus lanatus) The Missouri Watermelon Crop Profile was developed from interviews and surveys of key watermelon growers and brokers who manage approximately 25% of the production acreage in the state. Other information was gleaned from the Extension Vegetable Specialist at the University of Missouri. The third key information source was from census data and pesticide usage data obtained from USDA...»


«ITE SHEE H W T RA UB DI L O C FLYING HANDBOOK 2017 1 Welcome Welcome to Whitesheet Radio Flying Club. We hope that you will enjoy flying with us on our beautiful site and that you will enjoy the company of fellow members we like to think that we are a friendly club! If you have any queries or problems when on the slope make yourself known and someone will help you. Most of the information you require to benefit from membership of the Club is here in the Member’s Handbook. If there is...»

«BOARD OF SELECTPERSON’S MEETING PUBLIC HEARING FOR ORDINANCES AND CHARTER AMENDMENTS February 25, 2016 6:00 p.m. Rumford Falls Auditorium PRESENT: Chairperson Bradford Adley, Vice-Chairperson Jeffrey Sterling, Selectperson Frank DiConzo, Selectperson Mark Belanger, Selectperson Michael Peter Chase, Town Manager John Madigan, Jr. ATTENDEES: Bromley Cook 1. Meeting Call to Order by Chairperson Adley at 6:10 p.m. 2. Pledge of Allegiance to the American Flag 3. Approval of Charter Amendment...»

«Instructions for authors, permissions and subscription information: E-mail: bilgi@uidergisi.com Web: www.uidergisi.com Constructing Culturally Proximate Spaces through Social Network Services: The Case of Hallyu (Korean Wave) in Turkey Chong-Jin OH and Young-Gil CHAE* Prof. Dr., Hankuk University of Foreign Studies, Department of Turkish-Azerbaijani Studies * Prof. Dr., Hankuk University of Foreign Studies, Department of Media and Communications To cite this article: Oh, Chong-Jin and Young-Gil...»

«Duelist Pack Collection Tin 2010 – Card Rulings Compiled as of March 24th, 2010 version 1.0 Starlight Road DPCT-EN004 Activate only when an effect is activated that would destroy 2 or more cards you control. Negate the effect and destroy that card. Then, you can Special Summon 1 Stardust Dragon from your Extra Deck. You can only Chain this card directly to the effect that would destroy 2 or more cards you control. If you negate an effect with “Starlight Road” but cannot destroy the card,...»

«PLA PER A LA L’ADOLESCÈNCIA INFÀNCIA i L ADOLESCÈNCIA D’OLOT OLOT 20132013-2019 1 Ajuntament d’Olot Abril de 2013 NOTA 1: El Pla per a la infància i l’adolescència d’Olot 2013-2019 ha sigut aprovat pel Ple de l’Ajuntament d’Olot en la sessió tinguda el 25 d’abril de 2013, amb 19 vots favorables (CiU, PSC, ERC i PP) i una abstenció (PxC). Nota 2: La tipografia dels títols del pla és de l’Anna Vives, una noia amb la síndrome de Down, que ha creat la seva pròpia...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.