Let’sconsideraspecialcaseofQuantified3-SATinwhichtheunderlying Boolean formula has no negated variables. Specifically, let ( x 1, . , xn ) be a…

/in /by
  1. Let’sconsideraspecialcaseofQuantified3-SATinwhichtheunderlying Boolean formula has no negated variables. Specifically, let (x1, . . . , xn) be a Boolean formula of the form
  2. C1 ∧ C2 ∧ . . . ∧ Ck ,
  3. where each Ci is a disjunction of three terms. We say is monotone if each term in each clause consists of a nonnegated variable—that is, each term is equal to xi, for some i, rather than xi.
  4. We define Monotone QSAT to be the decision problem
  5. ∃x1∀x2 . . . ∃xn−2∀xn−1∃xn (x1, . . . , xn)? where the formula is monotone.
  6. Do one of the following two things: (a) prove that Monotone QSAT is PSPACE-complete; or (b) give an algorithm to solve arbitrary instances of Monotone QSAT that runs in time polynomial in n. (Note that in (b), the goal is polynomial time, not just polynomial space.)