Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
With the Circuit-SAT problem, I often see the "split" gate (I don't know the official name of it). This gate has a truth table of:
$$ \begin{array}{|c |c c|} 0 & 0 & 0\\ 1 & 1 & 1\\ \end{array} $$
And it has a symbol of this:
This gate allows us to use variable names more than once when we translate circuits to CNF.
I was wondering if the case where we didn't use this gate is still NP-complete. In other words, if we used every variable exactly once, would SAT still be NP-complete?
Each variable would appear twice - once as an output to a gate and once as an input.
It is trivial to start from the output and trace backwards, setting variables as you go, with a simple greedy algorithm. If the output has to be 1 then set it to 1. If the output of an AND or OR gate is 1 or 0, set all inputs to that same value; if the output of a NOT gate is 1 or 0, set the input to the opposite value. Go backwards from the circuit's output to the inputs until they are all set.
Without any splits in the circuit it is impossible to come to a situation where one path says an input should be 1 and another path says it should be 0, which would require backtracking to find an alternative solution. This can't happen because there is only one backwards path from the output to any variable.
