Key NP-Complete Problem Reductions: SAT, Clique & More

Posted on Dec 1, 2025 in Computer Engineering

CircuitSAT to SAT Reduction

Problem Checks

The Boolean Satisfiability Problem (SAT) is in NP because a given Boolean assignment serves as a polynomial-size certificate, which can be verified by evaluating the formula in polynomial time.

Reduction Construction

Given a circuit composed exclusively of NAND gates, the reduction proceeds as follows:

  1. Create a Boolean variable for each circuit input and for the output of each gate.
  2. For each gate represented as z = NAND(a,b), add Conjunctive Normal Form (CNF) clauses that enforce the logical equivalence z ↔ ¬(a ∧ b). This can be done with a small set of clauses (e.g., four clauses with three or fewer literals) that are satisfied only when z correctly represents the NAND of a and b.
  3. Assert that the final output variable of the circuit is True by adding a single-literal clause.

Correctness

Any assignment to the input variables can be extended by computing the gate outputs to determine the values for all gate variables. The clauses are constructed to be true if and only if each gate variable correctly represents the NAND of its inputs. Therefore, the circuit has an input that makes the final output True if and only if the constructed CNF formula is satisfiable. This construction runs in linear time relative to the circuit size.

SAT to 3-CNF-SAT (3SAT) Reduction

Problem Checks

3-CNF-SAT is in NP for the same reason as SAT: a satisfying assignment is a certificate that can be checked in polynomial time.

Reduction Construction

Given any CNF formula, we convert it into an equivalent 3-CNF formula by handling each clause based on its size:

  • Clauses with 3 literals: If a clause already has exactly three distinct literals, it is kept as is.
  • Clauses with fewer than 3 literals: These clauses are expanded. We introduce new, fresh variables to create one or more clauses of size three, ensuring the new group is satisfiable if and only if the original clause was.
  • Clauses with more than 3 literals: These clauses are broken down. We introduce new ‘helper’ variables to create a chain of 3-literal clauses that collectively enforce the original, longer clause’s constraint.

Correctness

Each transformation preserves satisfiability. Any satisfying assignment for the original variables can be extended to the new helper variables to satisfy the new 3-literal clauses. Conversely, any satisfying assignment for the new formula, when restricted to the original variables, satisfies the original formula. The entire transformation is completed in polynomial time.

3-CNF-SAT to Independent Set Reduction

Problem Checks

The Independent Set problem is in NP because a proposed set of vertices can be quickly verified by checking that no two vertices in the set are connected by an edge (i.e., they are pairwise non-adjacent).

Reduction Construction

For a given 3-CNF formula with m clauses, we construct a graph:

  1. For each clause, create a triangle of three vertices, with each vertex representing a literal in that clause. This ensures that at most one vertex from each triangle can be part of an independent set.
  2. Add an edge between any two vertices from different clauses that represent conflicting literals (e.g., one vertex for x and another for ¬x).
  3. Set the target size for the independent set, k, to be the number of clauses, m.

Correctness

  • Satisfiable Formula to Independent Set: If the formula is satisfiable, we can select one true literal from each clause. The corresponding m vertices form an independent set of size m. This is because only one vertex is chosen from each triangle, and no edges exist between them since the literals do not conflict.
  • Independent Set to Satisfiable Formula: Conversely, an independent set of size m must contain exactly one vertex from each clause-triangle. These vertices correspond to literals that do not conflict with each other. Assigning a ‘true’ value to these literals results in a satisfying assignment for the original formula.

This construction is performed in polynomial time.

Independent Set to Clique Reduction

Problem Checks

The Clique problem is in NP because a proposed subset of k vertices can be verified in polynomial time by checking that every pair of vertices in the subset is connected by an edge.

Reduction Construction

Given a graph G and an integer k, construct its complement graph, Ḡ. The complement graph Ḡ has the same set of vertices as G, but an edge exists between two vertices in Ḡ if and only if there is no edge between them in G. The integer k remains the same.

Correctness

A set of k vertices forms an independent set in G (meaning no edges exist between any pair) if and only if the same set of vertices forms a clique of size k in Ḡ (meaning all possible edges exist between them). Since constructing the complement graph is a polynomial-time operation, this demonstrates that Independent Set is reducible to Clique (Independent Set ≤P Clique).