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.

  • $\begingroup$ 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? $\endgroup$ – Mikhail Rudoy Jan 14 at 0:24
  • $\begingroup$ @MikhailRudoy Yes. That is why I name it barely, since there is only one satisfied but all others are not. $\endgroup$ – CO2 Jan 14 at 0:28
  • 1
    $\begingroup$ Barely-3-SAT is decidable in polynomial time. $\endgroup$ – Emil Jeřábek Jan 14 at 8:48

This problem can be solved in polynomial time.

Below, I describe a subroutine that checks for a given clause whether it is possible to satisfy only that clause. Since there are only polynomially many clauses, we can run this subroutine for every clause. Clearly the given formula is barely-satisfiable if and only if the subroutine returns true for some clause, so we can just OR all the subroutine outputs together to decide Barely 3-SAT.

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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.