We know that 1IN3SAT is np-complete , I will define an ne form of the SAT problem 2IN3SAT (exactly two true variables ). 2IN3SAT is np-complete because (x,y,z) is in 1IN3SAT iff (!x,!y,!z) is in 2IN3SAT ,

Let c be a new variable. For each clause (x,y,z) in a 2IN3SAT problem let the 7 clauses below forming a NAE3SAT problem. (x,y,z) ,(c,y,z) ,(x,c,z) ,(x,y,c) ,(!c,!y,!z) ,(!x,!c,!z) ,(!x,!y,!c) (*)

I think that, if we use the same c for all clauses of the initial 2IN3SAT the correspendant NAE3SAT will have the property. 2IN3SAT has a solution if and only if NAE3SAT has a solution.

Do you agree with this statement ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.