I know that monotone 3SAT is NPComplete. Also, 1 in 3SAT is NPComplete. I think both conditions together also leave the problem NP Complete (need confirmation).

If possible can someone please help with the smallest non trivial problem of this form that is unsatisfiable. Would be grateful.


How about $(x_1 \lor x_2 \lor x_3) \land (\bar{x}_1 \lor \bar{x}_2 \lor \bar{x}_3)$?

  • $\begingroup$ Thanks (sorry for the late response). But if possible could you help with an example that is not so obviously false. What I mean by that is some which we have to try and test to determine its false (for example with 7-8 variables). This is obviously false but its trivial. $\endgroup$
    – J.Doe
    Feb 9 '18 at 15:17
  • $\begingroup$ You can do it yourself. Generate random formulas and look at a few unsatisfiable ones. $\endgroup$ Feb 9 '18 at 15:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.