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:

enter image description here

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?

  • $\begingroup$ Each clause, being totally independent, can trivially be satisfied. $\endgroup$
    – Pål GD
    Apr 6 at 21:35

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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