1
$\begingroup$

$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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$ Apr 26, 2022 at 9:22
  • $\begingroup$ I bet that it works also for 3NAESAT. $\endgroup$ Apr 26, 2022 at 9:23

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.