Min-ones SAT is apparently NP-complete. I get that it is NP-hard (because SAT is trivially reduced in polynomial time to it), but I don't actually see how minimality can be verified in polynomial time.

Thus, my question: why is Min-Ones SAT in NP?

  • 1
    $\begingroup$ Perhaps you could explain what min-ones SAT is. $\endgroup$ – Yuval Filmus Jan 26 '19 at 3:24
  • $\begingroup$ I suspect that the real definition asks for the existence of a solution with at most a given number of ones. $\endgroup$ – Yuval Filmus Jan 26 '19 at 3:25
  • $\begingroup$ Adding to Yuval Filmus' comment, I believe it is vital for you to provide a definition here. Min-ones SAT is usually expressed as a search problem, so saying it is in NP (or NP-hard, etc.) is utter nonsense. If you mean the relation from your other post, then that can hardly be framed as NP-completeness since what you refer to is a Cook reduction, not a many-one reduction. $\endgroup$ – dkaeae Jan 28 '19 at 8:52

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.