Problem Definitions¶

In this section, we will examine several problems from the SAT family, which we will discuss later. The term SAT is an abbreviation for "satisfiability," meaning the ability to satisfy conditions. Each problem is a decision problem where we must provide an algorithm to determine whether the outputs can be arranged such that the input evaluates to 1 (true).

circuit-sat: In this problem, we are given a logical circuit composed of OR, AND, and NOT gates. This circuit has multiple inputs and exactly one output. The algorithm must determine whether there exists an assignment of inputs that makes the output equal to 1. Note that the circuits considered in this problem are combinational logic circuits, meaning they contain no cycles, and the output of a gate does not feed back into its inputs.

sat: This problem is a special case of the above, where the output is connected to a large AND gate, and each input of this AND gate is connected to a large OR gate. Each input of the OR gate is either a direct input variable or its negation. In other words, you are given an expression of the form: \((x_1 \lor x_7 \lor \overline{x_3}) \land ... \land (x_2 \lor \overline{x_1} \lor ... \lor x_7)\). You must determine whether the variables can be replaced with 0 or 1 such that the entire expression evaluates to 1. (The symbol resembling a "7" represents logical OR, the symbol resembling an "8" represents logical AND, and the line above a variable represents logical negation.)

3-sat: This problem is a special case of SAT where each parenthesis (clause) contains exactly 3 variables. Similarly, 2-sat is defined, and you will learn about its solving algorithm in later chapters.

Take an arbitrary NP problem. This problem has a polynomial-time verifier. Every verifier is itself a decision problem. The key insight is that any polynomial-time decision algorithm can be converted into a combinatorial logic circuit. While a rigorous proof of this requires deeper familiarity with algorithms and is beyond the scope of this book, you can experiment with it using familiar problems. For example, try designing a circuit for the verifier of the Hamiltonian cycle problem or the graph coloring problem.

Thus, for a fixed input length, we convert the decision procedure into a combinatorial logic circuit whose number of gates grows polynomially with the input size. Now, if we can provide the verifier with an input that satisfies it, we can also feed an input to its equivalent circuit to make its output 1. Therefore, the solution to the original problem is equivalent to the result of Circuit-SAT applied to this circuit. Hence, every problem in the NP class can be reduced to Circuit-SAT in polynomial time, making Circuit-SAT an NP-complete problem.

Reducing the circuit-sat Problem to sat¶

In this section, we will prove that the 3-sat problem is also an NP-complete problem, and consequently, its more general form, the sat problem, is also NP-complete. First, note that the exact three-variable requirement for clauses is not crucial, as clauses can be expanded by adding duplicate variables. For example,

\((x \lor \overline{y})\)

can be converted to

\((x \lor \overline{y} \lor \overline{y})\).

Now consider a combinational circuit. First, convert all AND or OR gates with more than two inputs into two-input gates. This increases the input size linearly, which is acceptable for our purposes. For each set of equipotential points (i.e., points connected by wires), we assign a variable. Then, for each gate, we add several constraints to enforce the gate’s behavior. These constraints ensure that the gate’s output corresponds to its inputs and its logical function. For example, suppose

\(a\)

and

\(b\)

are the inputs to an AND gate, and

\(x\)

is its output. By adding the constraints

\(\overline{a} \lor \overline{b} \lor x\),

\(a \lor \overline{x}\),

and

\(b \lor \overline{x}\),

we guarantee that the value of

\(x\)

is logically equivalent to the AND of

\(a\)

and

\(b\). Similarly, such constraints can be defined for OR and NOT gates. By taking the AND of all these constraints and the circuit’s output (which itself is a variable), we can construct a 3-sat instance whose satisfiability is equivalent to the circuit-sat problem. Thus, both this problem and its general form, sat, are NP-complete.