For this question you are to consider a new version of the
satisfiability problem, called XOR-SAT. This is just like CNF-SAT,
except that the “clauses” are made with the exclusive-or of
literals, not the usual “or.” An example is
For This Question You Are To Consider A New Version Of The Satisfiability Problem Called Xor Sat This Is Just Like Cnf 1 (53.37 KiB) Viewed 32 times
1. For this question you are to consider a new version of the satisfiability problem, called XOR-SAT. This is just like CNF-SAT, except that the "clauses" are made with the exclusive-or of literals, not the usual "or." An example is (x1x2x3) ^ (T1 T2 T3) a) Is the above formula satisfiable? Explain your choice. b) Show that XOR-SAT belongs to NP. c) Is XOR-SAT in P? Defend your answer. You should give either a proof of NP- completeness (which we will accept as convincing evidence for a "no" answer), or a polynomial-time algorithm.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!