Looking for any idea for reduction from $SAT \leq 3-SAT$ where $SAT$ is known to have $d$ variables at most in each clause. I am looking for a reduction in which the resulting formula will not depend on the value of $d$. The classical reduction adds $O(d)$ new variables per clause, so this is not good to my case.

Do such reductions even exist?

Edit: Even if it's impossible to find such reductions, maybe there are other interesting reductions which are not the classical one, they can also be interesting?

  • 1
    $\begingroup$ You can't have it not dependent on $d$. Consider just a single clause with $d$ different variables. After the reduction, it must have at least $\frac{d}{3}$ clauses, since each clause can "hold" only up to $3$ variables, and there are in total $d$ of them. $\endgroup$
    – nir shahar
    Dec 20 '21 at 20:56

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.