I am trying to prove the NP-Completeness of Min-satisfiability problem which can be defined as: Given a CNF formula (Set of clauses of 1 or more boolean variables) and a number x, there exists a satisfying assignment of those variables such that number of true variables in the assignment is less than or equal to x

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Apr 26 at 1:00
  • $\begingroup$ Choose an appropriate value of $x$. $\endgroup$ – Yuval Filmus Apr 26 at 4:56
  • $\begingroup$ I am able to prove that the problem is NP. For the NP-Hard part, I have tried to use vertex cover and k clique for the proof but I am not able to come up with anything concrete. I tried googling but I couldn't find min-sat or any similar problem. Any suggstions or hints would be appreciated $\endgroup$ – spiky Apr 26 at 5:16

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.