# Why is Min-ones SAT in NP?

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?

• Perhaps you could explain what min-ones SAT is. – Yuval Filmus Jan 26 at 3:24
• I suspect that the real definition asks for the existence of a solution with at most a given number of ones. – Yuval Filmus Jan 26 at 3:25
• 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. – dkaeae Jan 28 at 8:52