Waiting for answer This question has not been answered yet. You can hire a professional tutor to get the answer.
QUESTION
Let'sconsideraspecialcaseofQuantified3-SATinwhichtheunderlying Boolean formula has no negated variables. Specifically, let ( x 1, . , xn ) be a...
- 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.)
