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

Published by admin at August 12, 2023

Tags

Let’sconsideraspecialcaseofQuantified3-SATinwhichtheunderlying Boolean formula has no negated variables. Specifically, let (x1, . . . , xn) be a Boolean formula of the form
C1 ∧ C2 ∧ . . . ∧ Ck ,
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.
We define Monotone QSAT to be the decision problem
∃x1∀x2 . . . ∃xn−2∀xn−1∃xn (x1, . . . , xn)? where the formula is monotone.
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.)