Coping with Intractability

You have just proved your problem NP-complete. A weaker student sighs and gives up: "no polynomial algorithm exists, so there is nothing to be done." A stronger one smiles — because in the real world you rarely need to solve the general problem exactly and instantly. You need to route this delivery fleet, colour this register-interference graph, pack these particular boxes, tonight, well enough. An NP-completeness proof is not a tombstone; it is a signpost that says brute force will not scale — now choose which luxury to give up.

This page is the map of that choice. Every exact algorithm for an NP-hard problem secretly relies on all four of these being true at once: it is optimal, it works on every input, it runs in polynomial time, and it is deterministic. If \text{P} \neq \text{NP} you cannot keep all four. The whole art of coping is deciding, for your situation, which one you can most cheaply surrender.

The four things you can trade away

Think of intractability as a locked box with four hinges. You cannot open it head-on, but loosen any one hinge and the lid swings free. Each hinge is a whole sub-field of algorithms.

Give up…	…and you get	Idea in one line	Follow it up
Optimality	Approximation algorithms	Provably within a factor \rho of the best answer, in poly time.	Approximation algorithms
Guarantees	Heuristics & metaheuristics	Local search, simulated annealing, genetic algorithms — usually great, no promise.	see below
Generality	Special-case & parameterised algorithms	Fast whenever some parameter k (treewidth, solution size) is small.	Parameterised complexity & FPT
Speed	Exact exponential algorithms	Still exponential, but 2^n or 1.3^n beats n! by a universe.	Exact exponential algorithms
Determinism	Randomised algorithms	Flip coins; be right with high probability, or right in expected poly time.	Randomised algorithms
Worst case	Average-case tractability	The hard instances are vanishingly rare; typical inputs solve fast.	Average-case analysis

No single hinge is the "right" one — the choice is engineering, not mathematics. A compiler's register allocator quietly restricts to structured (chordal) interference graphs; a chip-placement tool runs simulated annealing overnight and takes what it gets; a SAT solver combines branch-and-bound with randomised restarts and routinely dispatches instances with millions of variables that are, in the worst case, hopeless.

Give up optimality: approximation and heuristics

The most disciplined surrender is optimality. An approximation algorithm runs in polynomial time and returns a solution guaranteed to be within a provable factor \rho of optimal — a 2-approximation for Vertex Cover never uses more than twice the minimum number of vertices, on any graph, always. That word "always" is what separates it from a heuristic.

A heuristic or metaheuristic — hill-climbing, tabu search, simulated annealing, genetic algorithms, ant-colony optimisation — also runs fast and is often stunningly good in practice, but offers no worst-case promise at all. You trade the certificate for flexibility: heuristics apply to messy real objectives that have no clean approximation theory. Rule of thumb: reach for an approximation algorithm when you need a guarantee to put in a contract; reach for a metaheuristic when you just need a good answer and the objective is ugly.

Give up generality: exploit the structure you actually have

"NP-complete" is a claim about the general problem. Your instances are almost never general. Two of the most powerful coping strategies both live here:

Special / structured inputs. Many NP-hard problems become polynomial on restricted graph classes. Independent Set is NP-hard in general but linear on trees; graph colouring is easy on interval graphs; 2-SAT is in P though 3-SAT is not. If your inputs come from a narrow world, find its name and steal its algorithm.
A small parameter. Parameterised complexity isolates a second quantity k — the solution size, the treewidth, the number of clauses to delete — and asks for running time f(k)\cdot n^{O(1)}. Vertex Cover with a budget of k vertices runs in O(2^k n): exponential only in the small knob, polynomial in the big one. When k is 15 and n is a million, that is the whole ballgame.

Give up speed (a little), or determinism, or the worst case

Sometimes you truly need the exact optimum — a provably minimum-cost chip layout, an exact model count. Then keep optimality and generality, and surrender polynomial time as gracefully as possible. Exact exponential algorithms squeeze the exponent: Held–Karp solves TSP in O(2^n n^2) instead of the n! of naive permutation search, and modern branch-and-bound with good pruning solves real instances far beyond what that worst case suggests.

Two subtler trades round out the toolbox. Randomisation gives up determinism: a coin-flipping algorithm can be simpler and faster, correct with probability you can drive as close to 1 as you like. And average-case tractability gives up the worst case: if the hard instances are astronomically rare, an algorithm that is exponential in theory can be effectively instant on the inputs you will ever actually see. This is why SAT and integer-programming solvers feel magical despite the grim theory.

Wonderfully, no — and this is one of the deepest surprises in the whole field. NP-completeness is about finding the exact optimum; approximation is a genuinely different, and often much easier, question. Some problems admit an approximation ratio as tight as you please (a PTAS); others have a fixed best-possible ratio; and — via the astonishing PCP theorem — some are provably as hard to approximate as to solve. So "how well can this be approximated?" carves the NP-hard problems into a rich hierarchy that "is it NP-hard?" cannot see at all.

The single most expensive misconception a working engineer can hold is that "NP-complete" means "give up." It does not. It means the general problem has no known algorithm that is simultaneously optimal, universal, fast and deterministic — a worst-case statement about an adversarially chosen input. Your input is not adversarial. TSP instances with tens of thousands of cities are solved to proven optimality daily; industrial SAT instances with millions of variables fall in seconds. Conversely, do not swing to the opposite error and assume a heuristic's good behaviour on your test set is a guarantee — only an approximation algorithm's proof, or an exact solver's certificate, gives you that. Know which one you have.

How to read this module

The pages ahead take the trades one at a time. Approximation algorithms makes "within a factor \rho" precise and builds the classic guarantees; Analysing approximation ratios shows how the proofs work and introduces PTAS/FPTAS; Hardness of approximation and the PCP theorem shows where approximation itself hits a wall; Parameterised complexity and FPT develops the small-parameter idea; and Exact exponential algorithms shows how to keep optimality while beating brute force. Keep the four-hinge picture in your head as you go — every technique is just one hinge, loosened well.