# Can I prove this polynomial reduction?

Consider Barely-3-SAT: given a CNF $$F=\wedge^m C_i$$ determine whether there is an assignment such that exactly one clause $$C_k$$ is true all the others are false. I want to show this is $$NP$$-complete. It is trivial that it is in $$NP$$. We try to deduce 3-SAT to it. Build $$m$$ formulae $$F_j=C_j\wedge w_k$$ with $$k\neq j, w_k=\overline{C}_k$$. Run Barely-3-SAT on each $$F_j$$. It is correct if only if all are true. The number of clauses is bounded polynomially. Then we have the proposition. But I do not think this is really equivalent, since I did not really deduce to Barely-3-SAT but several times of it.

• What do you mean when you ask for exactly one clause to be satisfiable? Are you trying to ask whether there exists a boolean assignment for the variables such that exactly one clause is satisfied? – Mikhail Rudoy Jan 14 at 0:24
• @MikhailRudoy Yes. That is why I name it barely, since there is only one satisfied but all others are not. – CO2 Jan 14 at 0:28
• Barely-3-SAT is decidable in polynomial time. – Emil Jeřábek Jan 14 at 8:48

The subroutine is simple. We are given a formula and a clause $$C$$ in that formula and want to determine whether it is possible to satisfy $$C$$ without satisfying any other clause in the formula. Consider every literal in the other clauses. In order for those other clauses to be unsatisfied, every such literal must be false. So for each literal, assign that variable the truth value that makes that literal false. If any variable is assigned two different literals in this way then it is impossible to make all the other clauses simultaneously unsatisfied. If under this assignment $$C$$ is false then it is impossible to simultaneously make $$C$$ satisfied and make all the other clauses unsatisfied. If under this assignment $$C$$ is true or the value of $$C$$ is undefined (i.e. if some variable involved in $$C$$ was not set) then it is possible to make $$C$$ satisfied while keeping the other clauses unsatisfied.