Circuit satisfiability problem

CircuitSAT is closely related to the Boolean satisfiability problem (SAT), and likewise, has been proven to be NP-complete. It is a prototypical NP-complete problem; the Cook–Levin theorem is sometimes proved on CircuitSAT instead of on the SAT, and then CircuitSAT can be reduced to the other satisfiability problems to prove their NP-completeness. The satisfiability of a circuit containing $m$ arbitrary binary gates can be decided in time $O (2^{0.4058 m})$ .

Proof of NP-completeness

Given a circuit and a satisfying set of inputs, one can compute the output of each gate in constant time. Hence, the output of the circuit is verifiable in polynomial time. Thus Circuit SAT belongs to complexity class NP. To show NP-hardness, it is possible to construct a reduction from 3SAT to Circuit SAT.

Suppose the original 3SAT formula has variables $x_{1}, x_{2}, \dots, x_{n}$ , and operators (AND, OR, NOT) $y_{1}, y_{2}, \dots, y_{k}$ . Design a circuit such that it has an input corresponding to every variable and a gate corresponding to every operator. Connect the gates according to the 3SAT formula. For instance, if the 3SAT formula is $(\neg x_{1} \land x_{2}) \lor x_{3},$ the circuit will have 3 inputs, one AND, one OR, and one NOT gate. The input corresponding to $x_{1}$ will be inverted before sending to an AND gate with $x_{2},$ and the output of the AND gate will be sent to an OR gate with $x_{3} .$

Notice that the 3SAT formula is equivalent to the circuit designed above, hence their output is same for same input. Hence, If the 3SAT formula has a satisfying assignment, then the corresponding circuit will output 1, and vice versa. So, this is a valid reduction, and Circuit SAT is NP-hard.

This completes the proof that circuit SAT is NP-Complete.

3 more chapters are free with a Lably account.

Planar circuit SAT

Assume that we are given a planar Boolean circuit (i.e. a Boolean circuit whose underlying graph is planar) containing only NAND gates with exactly two inputs. Planar Circuit SAT is the decision problem of determining whether this circuit has an assignment of its inputs that makes the output true. This problem is NP-complete. Moreover, if the restrictions are changed so that any gate in the circuit is a NOR gate, the resulting problem remains NP-complete.

Circuit UNSAT

Circuit UNSAT is the decision problem of determining whether a given Boolean circuit outputs false for all possible assignments of its inputs. This is the complement of the Circuit SAT problem, and is therefore co-NP-complete.

Reduction from CircuitSAT

Reduction from CircuitSAT or its variants can be used to show NP-hardness of certain problems, and provides us with an alternative to dual-rail and binary logic reductions. The gadgets that such a reduction needs to construct are:

A wire gadget. This gadget simulates the wires in the circuit.
A split gadget. This gadget guarantees that all the output wires have the same value as the input wire.
Gadgets simulating the gates of the circuit.
A true terminator gadget. This gadget is used to force the output of the entire circuit to be true.
A turn gadget. This gadget allows us to redirect wires in the right direction as needed.
A crossover gadget. This gadget allows us to have two wires cross each other without interacting.

Minesweeper inference problem

This problem asks whether it is possible to locate all the bombs given a Minesweeper board. It has been proven to be co-NP-complete via a reduction from circuit UNSAT problem. The gadgets constructed for this reduction are: wire, split, AND and NOT gates and terminator. There are three crucial observations regarding these gadgets. First, the split gadget can also be used as the NOT gadget and the turn gadget. Second, constructing AND and NOT gadgets is sufficient, because together they can simulate the universal NAND gate. Finally, since three NANDs can be composed intersection-free to implement an XOR, and since XOR is enough to build a crossover, this gives us the needed crossover gadget.

The Tseytin transformation

The Tseytin transformation is a straightforward reduction from Circuit-SAT to SAT. The transformation is easy to describe if the circuit is wholly constructed out of 2-input NAND gates (a functionally-complete set of Boolean operators): assign every net in the circuit a variable, then for each NAND gate, construct the conjunctive normal form clauses (v₁ ∨ v₃) ∧ (v₂ ∨ v₃) ∧ (¬v₁ ∨ ¬v₂ ∨ ¬v₃), where v₁ and v₂ are the inputs to the NAND gate and v₃ is the output. These clauses completely describe the relationship between the three variables. Conjoining the clauses from all the gates with an additional clause constraining the circuit's output variable to be true completes the reduction; an assignment of the variables satisfying all of the constraints exists if and only if the original circuit is satisfiable, and any solution is a solution to the original problem of finding inputs that make the circuit output 1. The converse—that SAT is reducible to circuit-SAT—follows trivially by rewriting the Boolean formula as a circuit and solving it.