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?

  • 2
    $\begingroup$ If SAT is in P then P=NP and so any NP problem is in P. $\endgroup$ – Yuval Filmus Jan 25 '19 at 18:32
  • $\begingroup$ @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) $\endgroup$ – Drew Brady Jan 25 '19 at 18:57
  • 1
    $\begingroup$ You can implement a counter and so get a many-one reduction . Details left to you. $\endgroup$ – Yuval Filmus Jan 25 '19 at 19:00
  • 1
    $\begingroup$ 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). $\endgroup$ – Yuval Filmus Jan 25 '19 at 19:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 25 '19 at 19:11

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.