3
$\begingroup$

For the purpose of this post, let $k$-SAT be SAT with exactly $k$ literals per clause, as opposed to the more common meaning of at most $k$ literals per clause.

With the purpose of proving some problem NP-hard, I'd like to reduce from a $k$-SAT variant (which of course should remain NP-hard) in which each variable occurs exactly $\ell$ times in the formula.

I've tried to look up 3-SAT with exactly 3 occurrences of a variable, but this paper proves 3-SAT with at most 3 occurrences per variable is trivial, which includes my specific case of exactly 3 occurrences. (In fact, this is the case whenever $k = \ell$.)

All hope is not lost though, as in the same paper, it is proven that 3-SAT with at most $\ell$ occurrences per variable, with $\ell>3$ is NP-hard. I'm looking into the details of the reduction to see if by chance they have proved the specific case of exactly $\ell$ occurrences per variable to be NP-hard (which would extend to the general case of at most $\ell$ occurrences per variable), but wanted to ask this question here while searching:

Does there exist an NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The problem of deciding the satisfiability of 3CNFs in which each variable occurs exactly 5 times is NP-complete (and even NP-hard to approximate), see Uriel Feige, A threshold of $\ln n$ for approximating Set Cover.

Improve this answer
$\endgroup$
1
  • $\begingroup$ For anyone clicking on the link and wondering: MAX-SNP hardness implies NP hardness. $\endgroup$
    – J. Schmidt
    Commented Oct 21, 2022 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.