Skip to main content
5 of 5
edited tags
Kaveh
  • 22.5k
  • 4
  • 52
  • 112

How much can we reduce the number of clauses by converting from $k$-SAT to $(k+m)$-SAT?

If we suppose that we start with an instance of $k$-SAT, and try converting the problem to an instance of $(k+m)$-SAT, where there are $(k+m)$ literals per clause, can we guarantee a reduction in the total amount of clauses?

I realized after posting that we can't guarantee that the number of clauses can be reduced. However, I wonder if we have $n$ clauses, could we get something like $n/k + O(1)$ clauses by some "reduction" technique?

If so, how much can we guarantee the total number of clauses can be reduced by? For instance, if we start with $k$-SAT with $n_k$ clauses, what is the smallest guaranteed $n_{k+m}$, the new amount of clauses, that will result if we convert this instance to $(k+m)$-SAT?

More importantly, how do we carry out this conversion?

Matt Groff
  • 892
  • 1
  • 7
  • 16