3-SAT is an NP-Complete problem. Now given a 3-SAT instance it can be transformed to a Monotone-1-in-3 SAT instance thus even Monotone-1-in-3-SAT is NP-Complete (am aware of this reduction).

But, as I have read (forgot the source) even Cubic-Monotone-1-in-3-SAT is NP-Complete. Assuming given a Monotone-1-in-3-SAT instance how do we reduce it to the 'Cubic-Monotone' version i.e. each boolean variable in the 1-in-3-SAT instance occurs exactly 3 times and only positively.

Can someone please help with this reduction (as simple as possible)?

I tried thinking and searching but couldn't find any simple reduction.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.