P, NP, NP-Hardness & Polynomial-Time Reductions (3-SAT ≤p Independent Set ≤p Vertex Cover ≤p Subset Sum)

1. Formal Invariant — Complexity Classes & Karp Reduction Direction

2. Karp's Canonical Reduction Chain (1972)

3. Anatomy of the Core Reductions

1. $\text{3-SAT} \le_p \text{Independent Set}$: Given a 3-CNF formula with $m$ clauses, create a triangle of $3$ vertices for each clause (so any independent set can pick at most $1$ vertex per triangle, max $m$ vertices total). Add conflict edges between every literal $x_i$ and its negation $\neg x_i$ across all clauses. Then the graph has an Independent Set of size $K = m$ if and only if one true literal can be chosen from every clause without contradiction!
2. $\text{Independent Set} \equiv_p \text{Vertex Cover}$ (Gallai's Identity): In any graph $G = (V, E)$, a subset $I \subseteq V$ has no internal edges (Independent Set) if and only if its complement $S = V \setminus I$ touches every edge in $E$ (Vertex Cover)! Thus $\alpha(G) + \tau(G) = |V|$.
3. $\text{Vertex Cover} \le_p \text{Subset Sum}$: Encode each vertex $v_i$ and edge $e_j$ as digits in a base-4 number with $|E| + 1$ columns (column $0$ has weight $4^{|E|}$ counting chosen vertices, and column $j$ tracks how many endpoints cover edge $e_j$). Adding a slack number $4^{j}$ per edge allows reaching target sum $K \cdot 4^{|E|} + \sum_{j=0}^{|E|-1} 2 \cdot 4^j$ with zero carry between columns iff a Vertex Cover of size $K$ exists!

4. Strong NP-Completeness vs Weak (Pseudo-Polynomial) NP-Completeness

5. Complexity Matrix: Tractable Twins vs NP-Complete Counterparts

6. Production-Grade C++20 Implementation (Karp Reduction $\text{3-SAT} \to \text{Independent Set}$)

#include <vector>
#include <utility>
#include <cmath>

struct Clause3 {
    // Literals encoded as +var (1..num_vars) or -var (-1..-num_vars)
    int lit[3];
};

struct IndependentSetInstance {
    int num_vertices;
    int target_k;
    std::vector<std::pair<int, int>> edges;
};

// Polynomial-time Karp reduction: 3-SAT (m clauses) <=_p Independent Set (3m vertices, K = m)
IndependentSetInstance reduce_3sat_to_independent_set(const std::vector<Clause3>& clauses) {
    const int m = static_cast<int>(clauses.size());
    IndependentSetInstance out;
    out.num_vertices = 3 * m;
    out.target_k = m;

    // 1. Add triangle edges inside each clause c (at most 1 vertex chosen per clause)
    for (int c = 0; c < m; ++c) {
        int u0 = 3 * c, u1 = 3 * c + 1, u2 = 3 * c + 2;
        out.edges.emplace_back(u0, u1);
        out.edges.emplace_back(u1, u2);
        out.edges.emplace_back(u0, u2);
    }

    // 2. Add conflict edges between complementary literals (x and -x)
    for (int c1 = 0; c1 < m; ++c1) {
        for (int i = 0; i < 3; ++i) {
            for (int c2 = c1 + 1; c2 < m; ++c2) {
                for (int j = 0; j < 3; ++j) {
                    if (clauses[c1].lit[i] == -clauses[c2].lit[j]) {
                        out.edges.emplace_back(3 * c1 + i, 3 * c2 + j);
                    }
                }
            }
        }
    }
    return out;
}