# relationship between SAT and Min-ones SAT

If SAT can be decided in polynomial time, is it clear that Min-ones SAT can be decided in polynomial time? The idea I had was to take a poly decider of SAT and try it on a formula OR'd with all settings of the variables with exactly $$k$$ ones. If it is satisfiable for $$k = 1$$, then we know the Min-ones SAT on the formula with $$k = 1$$ should be accepted. Else, we increment $$k = 2$$, and repeat again. This is at worst $$n$$ calls to SAT decider, so it would be polynomial time, BUT the caveat is that you have to write down the formula or'd with all settings of exactly $$k$$ ones, of which there are $$\binom{n}{k}$$. In the worst case, this could take exponential time to write down, so I don't think this works. But perhaps there's another way to do it?

• If SAT is in P then P=NP and so any NP problem is in P. – Yuval Filmus Jan 25 '19 at 18:32
• @YuvalFilmus, I agree, I was just wondering if there was a way to see this without appealing to the Cook-Levin theorem (i.e., without using that SAT is NP complete) – Drew Brady Jan 25 '19 at 18:57
• You can implement a counter and so get a many-one reduction . Details left to you. – Yuval Filmus Jan 25 '19 at 19:00
• The counter will count the number of ones in the assignment. You can then assert that it’s value is $k$. You can implement either a unary counter (easier) or a binary counter (more succinct). – Yuval Filmus Jan 25 '19 at 19:05
• You add to the SAT instance the constraint of having exactly $k$ ones, which you can encode by implementing a counter. You will get a many-one reduction. – Yuval Filmus Jan 25 '19 at 19:11