Nine entries on this site run into the same wall: 0/1 Knapsack, Fractional Knapsack, Set Cover, Steiner Tree, Graph Coloring, Hamiltonian Path, 2-SAT, DPLL, and Dancing Links are all built around a problem that is, in its general form, NP-hard (optimization) or NP-complete (decision) — no known algorithm finds the exact right answer on every input in better than exponential worst-case time, and none is believed to exist. Each page already says this about itself. None of them says that "NP-hard, now what?" actually has four genuinely different answers on this site, not one — and which answer applies depends entirely on which part of the original promise a problem is willing to give up: the problem itself, true polynomial time, exactness, or the worst case. Every claim below is a number or a quote each source page already proved or measured; this page only lines the four responses up side by side for the first time.
The cheapest way to escape NP-hardness is to not solve the hard version at all — change one rule of the problem and the entire complexity class can fall away. Two pairs on this site do this by two genuinely different knobs.
2-SAT restricts structure. General boolean
satisfiability — three or more literals per clause — is the textbook NP-complete problem, the same
one DPLL attacks head-on below. Capping every clause at exactly
two literals removes the wall entirely: 2-SAT's own Complexity section runs the decision in O(V + E), by translating clauses into an
implication graph and handing the real work to Strongly Connected Components. Nothing
about how the search runs changed — the two-literal cap just removes the combinatorial
explosion before any search is needed.
Fractional Knapsack relaxes a
constraint instead. 0/1 Knapsack is NP-hard because every item is indivisible — take it
whole or leave it. Drop that one rule, let items split, and the identical-looking problem becomes
exactly solvable by a single greedy pass: rank by value-per-weight, fill until the knapsack is full,
split the last item to hit the cap exactly. Fractional Knapsack's own Complexity section is blunt
about why: "O(n log n),
entirely the cost of sorting by ratio... no table, no backtracking, no exponential worst case
anywhere — a direct consequence of the proof above rather than a coincidence." Relaxing
integrality, not restricting structure, is what buys the escape this time — a different knob
reaching the same kind of exit.
0/1 Knapsack itself doesn't escape NP-hardness this way —
it solves the real indivisible problem, exactly, every time, with a dynamic-programming table sized
(n+1) × (capacity+1). That looks like a polynomial escape, O(n · capacity),
until its own Pitfalls section names the catch: "the bound depends on the numeric value of the capacity,
not the size of its representation — writing '1,000,000' takes seven characters but produces a
million-column table... algorithms whose cost scales with a number's magnitude rather than its
input size are called pseudo-polynomial — genuinely fast enough at the sizes this
page's demo runs at, but not a counterexample to 0/1 knapsack's status as a classic NP-hard problem
in general." This is a third thing, not a weaker version of the first two: every answer is
exact, forever, on every input — but double every weight and the capacity, and the identical
problem suddenly costs twice the table, something a true polynomial algorithm would never notice.
Set Cover and Steiner Tree take the opposite trade: never claim the true
optimum, but prove — not hope, prove — exactly how far off the answer can ever be, on every input,
no exceptions. Set Cover's own greedy rule (repeatedly pick whichever remaining set covers the most
still-uncovered elements) is bounded by a pigeonhole argument over the true optimum's own size,
landing on a guaranteed O(OPT · ln n) sets,
never more — its own page calls this "the site's first genuine approximation algorithm in the
strict sense, rather than a correct-or-heuristic rule." Steiner Tree's 2-approximation reuses Kruskal's algorithm on the terminals' own shortest-path metric
closure, and its Complexity section is equally explicit that the general problem is "NP-hard, with no known polynomial algorithm that
always finds the true minimum" — exactly the gap the 2-approximation is built to bound, not
dodge. Both guarantees hold on every input, adversarial or not — that's what separates an
approximation algorithm from a heuristic that merely tends to do well (see Pitfalls below for the
contrast, measured on Set Cover's own page).
Graph Coloring (k ≥ 3), Hamiltonian Path, DPLL (general SAT), and Dancing Links (exact cover) all take the fourth option:
solve the real problem, exactly, and don't pretend the worst case is anything but exponential. Each
page says this about itself in nearly identical words — Graph Coloring's Complexity section: "pruning cuts the constant factor dramatically...
but doesn't change the underlying order, and for k ≥ 3 there's no known polynomial
algorithm and none is believed to exist, since the problem is NP-complete." DPLL's: "unit propagation and pure-literal elimination shrink the
constant factor in practice, sometimes dramatically... never the underlying order." Dancing
Links makes the same point with an actual measured number instead of just the claim: its own
pointer-relinking trick drops each cover/uncover step to O(k) instead of
O(rows × columns) for a naive scan-and-copy implementation — a real, substantial
engineering win — while its Complexity section is equally clear that "no column-choice rule changes
the underlying order, only the constant factor." All four pages are proof that "exponential worst
case" and "unusably slow in practice" are not the same claim — small or well-structured instances on
every one of these pages resolve instantly — but neither is a smarter pruning rule a path out of the
complexity class itself.
The four rows below use each strategy's own already-proven worst-case formula from the sections
above, evaluated at a shared stand-in problem size n — not a claim that an
n-variable 2-SAT instance does the same real-world work as an n-item
Knapsack problem. 2-SAT's row is its own real O(V+E) bound; Set Cover's is its own
O(m²n) bound with the candidate-set count m set equal to n for
illustration; 0/1 Knapsack's is its own O(n · capacity) bound with the capacity fixed
at a representative 1,000; the exponential row is the shared O(2ⁿ) every one of the
four exact-search pages above already states about itself. This is the same move How Fast Is Big-O, Really? already makes for abstract
complexity classes — here it's attached to four real algorithms on this site instead.
"NP-hard means nothing fast exists." It means no known algorithm finds the exact answer on every input in polynomial time. It forbids none of the four escape routes above: a fast exact algorithm for a restricted or relaxed version of the same-looking problem (2-SAT, Fractional Knapsack), a fast exact algorithm that's merely pseudo-polynomial rather than truly polynomial (0/1 Knapsack), a fast approximate algorithm with a proven ceiling (Set Cover, Steiner Tree), or a worst-case-exponential exact algorithm that's fast on most real instances anyway (every page in the previous section).
"Pseudo-polynomial is basically polynomial, just a technicality." 0/1 Knapsack's
own Pitfalls section measures the difference directly: double every weight, value, and the capacity
and the problem is identical in every meaningful sense, but the DP table this page builds doubles
in size. A true polynomial algorithm's cost depends on how many numbers are in the input, never on
how large those numbers are — Fractional Knapsack's O(n log n) sort genuinely doesn't
care whether the weights are single digits or seven-digit figures; 0/1 Knapsack's table does.
"A better pruning rule eventually fixes the exponential blowup." Dancing Links'
own O(k)-per-step trick over a naive O(rows × columns) rescan is a real,
measured, substantial speedup — and its own Complexity section is explicit that it changes "the
cost of each individual cover/uncover," never the exponent. Graph Coloring and DPLL say the
identical thing about their own pruning. None of this is a weaker form of the approximation
guarantees above — it's a different, smaller kind of win (constant factor, not complexity class).
"A proven approximation ratio is just a heuristic that happens to work well." Set
Cover's own Pitfalls section demonstrates the real difference on its own data: switching to a
plausible-looking "smallest set first" rule produces a worse cover (4 sets) than the proven
greedy rule (3 sets) on the identical input, with nothing bounding how much worse a differently
unlucky heuristic could do. The greedy rule's O(OPT · ln n) ceiling, by contrast, holds
on every input, adversarial or not — that's the entire difference between an approximation
algorithm and a heuristic that merely tends to do well.