# Hardness of 3SAT-k

According to these scribe notes (and a paper), 3SAT-5 is NP-hard. The problem is defined to be: given a 3SAT formula, each variable occurs in at most 5 clauses. It is also proven that 3SAT-4 is NP-hard.

What is the computational complexity of 3SAT-$k$ for $k \le 3$?

Theorem 2.4: Every instance of $r,r$-SAT is satisfiable.
This implies that 3SAT-$3$ is satisfiable.
In addition, Section 3 gives polynomial algorithm for the 2-occurrence case for any $m$-SAT instances ($m \ge 2$).
This implies that 3SAT-$\le 2$ is polynomially tractable.
• Thank you, I didn't see the $r,r$-SAT in the paper. – Ryan Jan 13 '15 at 3:28