# Proving the NP hardness of two variants of SAT

$$k$$-$$\text{RSAT}$$ is a variant of $$k$$-$$\text{SAT}$$ where we restrict our attention to formulae in which each variable occurs at most $$3$$ times, and each literal occurs at most twice. The language $$k$$-$$\text{RSAT}$$ is $$\{\phi \in k{-}\text{SAT} \mid \text{ no variable (literal) occurs more than 3 (2) times in }\phi \}.$$

$$k$$-$$\text{NAESAT}$$ is a variant of $$k$$-$$\text{SAT}$$ where we allow only assignments in which at least one literal in each clause evaluates to $$0$$.

I'm trying to prove that $$k$$-$$\text{RSAT}$$ and $$3$$-$$\text{NAESAT}$$ are $$\text{NP}$$ hard. If it helps, the previous subpart to this problem involved proving that $$k$$-$$\text{NSAT}$$ (defined below) is $$NP$$ hard (which I've proven).

$$k$$-$$\text{NSAT}$$ is a variant of $$k$$-$$\text{SAT}$$ where, given a $$k{-}\text{CNF}$$ formula $$\phi$$ and a natural number $$n$$, the problem is to determine if there exists an assignment for which at least $$n$$ clauses of $$\phi$$ evaluate to 1

How do I prove this?

The idea is to use a gadget that lets you copy variables. Given a variable $$x$$, there is a gadget that allows you to create a copy of $$x$$, that is, a new variable $$x'$$ such that any satisfying assignment of the gadget satisfies $$x = x'$$. Using your gadget, you create enough copies of each variable, and then replace each occurrence of a variable by a single copy of the variable.
• I added a small edit to my question, I'm trying to prove that $3-NAESAT$ is $NP$ hard (Not $k-NAESAT$, I have a proof for $4-NAESAT$). Your idea seems to work for $k-RSAT$ but I can't think of how to apply it to $3-NAESAT$? Apr 26, 2022 at 9:22