Prove 20-3-SAT is NP-Complete

Question

so I have this problem that I can't figure out.
20-3-SAT={All satusfiable 3-CNF formulas where each variable appears at most 20 times}

I was able to prove it's in NP using verifier, but for NP-Hard proof I'm having a little trouble. I tried to prove $3SAT\leq_p20-3SAT$ so that for a given formula, I can compose a new equivalent one with at most 20 copies for each variable.
But I'm not sure how to do it. Can anyone help me with this?

Thanks!

Answer 1

Suppose variable $v$ appears in $n$ clauses in the 3-CNF. We reduce the number of occurrences of $v$ as follows:

1. In clause $i$ ($1\le i\le n$) replace all instances of $v$ by a new variable $v_i$.
2. For $1\le i\le n-1$ add new $3$-clauses $v_i\lor\neg v_{i+1}\lor z$ and $\neg v_i\lor v_{i+1}\lor z$, enforcing that $v_i=v_{i+1}$. Each appearance of $z$ in these clauses is itself a distinct variable only appearing in one other clause $\neg z\lor\neg z\lor\neg z$, enforcing $z=0$.

After converting all variables of the original 3-CNF, each $v_i$ appears at most $3+2+2=7$ times and each $z$ appears at most $1+3=4$ times, so we have a 7-3-CNF equivalent to the original 3-CNF. Since the conversion can clearly be done in poly-time (and poly-space), 7-3-SAT is NP-complete.