Exact / NP-Hard

When the problem is genuinely hard and $n$ is genuinely small, you stop looking for a polynomial algorithm and start looking for a smart exponential one.

Exponential budget

Technique	Feasible n
Brute force $O(n!)$	10–11
Bitmask DP $O(2^{n}n)$	20–23
Bitmask DP $O(2^n{n}^2)$	18–20
Meet in the middle $O(2^{n/2})$	40–45
Branch and bound with good pruning	50–100 (problem dependent)
Subset sum with bitset $O(nW/64)$	$nW\approx 10^{10}$

• Backtracking
• Branch and Bound
• Meet in the Middle
• Exact Cover · Algorithm X · Dancing Links
• NP-Completeness and Reductions
• SAT and 2-SAT
• Maximum Clique and Independent Set · Bron-Kerbosch
• Graph Colouring
• Steiner Tree · Dreyfus-Wagner
• Travelling Salesman · Held-Karp
• Parameterized Complexity and Kernelization

See also: Complexity Theory · Randomized / Approximation