0
$\begingroup$

With the purpose of proving my problem NP-hard, I'd like to reduce from a SAT variant (which of course should remain NP-hard) in which not two parameters are present (typically $n$ clauses and $m$ variables) but only one, so $n$ clauses and $f(n)$ variables, for some function $f$.

I've tried to look up 3-SAT (SAT with exactly 3 literals per clause) with exactly 3 occurrences of a variable, as this would imply I'd have $n$ clauses and $n$ variables which would be perfect. Alas, this paper proves 3-SAT with at most 3 occurrences per variable is trivial, including my specific case of exactly 3 occurrences.

All hope is not lost though, as in the same paper, it is proven that 3-SAT with at most $k$ occurrences per variable, with $k > 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 $k$ occurrences per variable to be NP-hard (which would extend to the general case of at most $k$ occurrences per variable), but wanted to ask this question here while searching:

Does there exist an NP-hard SAT variant with $n$ clauses and $f(n)$ variables?

EDIT: the answer is yes, there exists such an NP-hard SAT variant, see this post, so I'd like to modify this question just for the sake of it:

Does there exist an NP-hard 3-SAT variant with $n$ clauses and $f(n)$ variables?

(As a reminder, In this post 3-SAT means exactly 3 literals per clause, as opposed to the more common meaning of at most 3 literals per clause, used in the solution for my first question.)

$\endgroup$

1 Answer 1

2
$\begingroup$

General 3-SAT is reducible to 3-SAT with $n$ clauses and $3n$ variables, as more variables would mean one isn't even present in some clause and can be removed, which can be done linearly.

Conversely it's also equivalent to 3-SAT with $m$ variables and $m(m+1)(m+1)/6$ clauses, as otherwise some clauses would be redundant, and again this can be checked in linear time.

$\endgroup$
1
  • $\begingroup$ I forgot another detail, occurrence! Your answer is of course correct w.r.t. the question I asked, so I will start a new post instead of modifying my question and cheating you out of the answer... $\endgroup$
    – J. Schmidt
    Commented Oct 20, 2022 at 14:00

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.