NPC Reduction Logic

SAT -> 3SAT

Goal
Gadget
IFF Statement
Logic
Closing Statement

The Goal: Convert clauses with n literals into clauses with exactly 3.

The Gadget: Use n-3 auxiliary helper variables (y_i) to chain long clauses together.

The IFF Statement: The original formula is satisfiable iff there exists an assignment for the y variables that allows the 3-literal chain to be satisfied simultaneously.

Logic Summary: If one original literal is True, the y variables can be "flipped" to satisfy the rest of the chain; if all original literals are False, the chain cannot be satisfied.

Closing Statement: This reduction preserves satisfiability by using auxiliary variables to break down complex constraints without adding exponential complexity.

3SAT -> Independent Set (IS)

Gadget
Edges
Target
IFF Statement
Logic
Closing Statement

The Gadget: Each clause becomes a 3-node triangle.

The Edges: 1. Connect all nodes within each triangle. 2. Connect each literal x to all its negations (NOT x) in other triangles.

Target k: k = m (number of clauses).

The IFF Statement: The 3SAT formula is satisfiable iff the graph has an Independent Set of size m.

Logic Summary: You must pick exactly one node per triangle to avoid internal edges; picking x in one triangle prevents picking NOT x in any other.

Closing Statement: This maps logical consistency directly to spatial distance in a graph, proving that choosing non-conflicting truths is equivalent to picking non-adjacent nodes.

3SAT -> Vertex Cover (VC)

The Gadget: 1. Variable Gadgets: An edge (x --- NOT x) for each variable. 2. Clause Gadgets: A 3-node triangle for each clause.

Target k: k = n + 2m (n = variables, m = clauses).

The IFF Statement: The formula is satisfiable iff the graph has a Vertex Cover of size n + 2m.

Logic Summary: You must pick 1 node from each variable edge and 2 nodes from each clause triangle. This leaves over one "free" literal per triangle to satisfy the 3SAT clauses.

Closing Statement: This reduction forces a choice between literals and ensures that the nodes NOT in the cover in each clause triangle correspond to a valid satisfying assignment.

3SAT -> Clique

The Gadget: Create m clusters of 3 nodes (one cluster per clause).

The Edges: Connect every node to every other node EXCEPT: 1. Nodes in the same cluster. 2. Contradictory literals (e.g., x and NOT x).

Target k: k = m (number of clauses).

The IFF Statement: The formula is satisfiable iff the graph has a Clique of size m.

Logic Summary: To get a clique of size m, you must pick exactly one node from each cluster such that no two nodes contradict each other.

Closing Statement: Finding a Clique in this construction is equivalent to picking one compatible literal from every single clause.

Independent Set -> Clique

The Construction: Create the complement graph G-bar (keep vertices, but flip all edges: existing edges disappear, non-edges become edges).

Target k: k(Clique) = k(IS).

The IFF Statement: G has an Independent Set of size k iff G-bar has a Clique of size k.

Logic Summary: An Independent Set is defined by a total lack of edges; flipping the graph turns that "void" into a perfectly connected Clique.

Closing Statement: This proof demonstrates that Clique and Independent Set are mathematically identical problems viewed from opposite perspectives.

Independent Set -> Vertex Cover (VC)

The Construction: Use the exact same graph G (no changes to edges or nodes).

Target k: k(VC) = Total Vertices - k(IS).

The IFF Statement: S is an Independent Set of size k iff (Vertices minus S) is a Vertex Cover of size (Total Vertices - k).

Logic Summary: If no two nodes in S share an edge, then every edge in the graph must have at least one of its endpoints sitting in the "other" set.

Closing Statement: This utilizes the mathematical property that a vertex cover is the complement of an independent set within the same graph.

3SAT -> Subset Sum

The Gadget: A matrix of numbers in base-10. Rows represent True/False literals and slack for clauses. Columns represent variables and clauses.

Target T: A number with 1s in variable columns and 3s in clause columns.

The IFF Statement: The formula is satisfiable iff a subset of these numbers sums exactly to the target T.

Logic Summary: Summing to 1 in variable columns forces a choice between x and NOT x. Summing to 3 in clause columns ensures at least one literal is True per clause.

Closing Statement: This encodes logical constraints into specific decimal positions, proving that simple addition is powerful enough to solve boolean logic.