Algorithm Design Paradigms

Reductions & Intractability

A reduction transforms one problem into another so that solving the target solves the original. Reductions are how new NP-complete problems are discovered, and how a real-world problem is recognized as (probably) intractable before wasting effort on an exact algorithm.

A reduces to B means: given a solver for B, you can solve A with only polynomial extra work — B is "at least as hard" as A
Proving a new problem NP-complete: show it's in NP (a solution can be verified in polynomial time), then reduce a known NP-complete problem to it
Recognizing your problem resembles Traveling Salesman, Knapsack, SAT, Vertex Cover, or Graph Coloring is a strong signal that no polynomial exact algorithm is likely to exist (Complexity Classes)
Practical response to intractability: approximation algorithms (provably close to optimal), heuristics (no guarantee, works well in practice), restricting to special-case inputs, or exponential/backtracking search with strong pruning
Reductions are also a design tool outside complexity theory: solving A "for free" by transforming it into a shape an existing library or algorithm already solves

The practical skill here is pattern recognition, not the formal proof machinery. Given a new problem, the question worth asking early is: does this look like a disguised version of a problem already known to be NP-complete? Scheduling with resource constraints often hides Bin Packing or Knapsack; "assign X to Y such that no conflicts" problems often hide Graph Coloring; anything with a "visit every node/take every item exactly once, minimize cost" shape often hides TSP. Recognizing the shape early prevents sinking weeks into an exact polynomial algorithm that (almost certainly) does not exist.

A reduction in practice: Vertex Cover via a SAT-style encoding sketch

// "Does this graph have a vertex cover of size <= k?" reduces cleanly to
// "is this boolean formula satisfiable?" — one boolean variable per (vertex, position in cover),
// clauses encoding "every edge has at least one endpoint chosen" and "exactly k vertices chosen".
// A generic SAT solver then solves Vertex Cover for free — at the cost of exponential
// worst-case time inherited from SAT itself; the reduction proves equivalence, not tractability.
boolean hasVertexCoverOfSize(Graph g, int k) {
    CnfFormula formula = encodeVertexCoverAsSat(g, k);
    return satSolver.isSatisfiable(formula);
}

The reduction is the useful, reusable idea — the exponential cost is what it proves is (probably) unavoidable

When exact is out of reach
Strategy	Guarantee	Example
Approximation algorithm	provably within a factor of optimal	2-approximation for Vertex Cover
Heuristic	none — empirically good	nearest-neighbor for TSP
Exponential search with pruning	exact, but possibly slow	Backtracking for small instances
Restrict the input	exact and fast, narrower problem	TSP on a tree, 2-SAT instead of general SAT