Answered>Order 3773

  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.) 
 
"Not answered?"
Get the Answer
/by