NP-Hard problems have no known polynomial-time algorithm. This does not mean they are completely unsolvable — it means:
- Exact optimal solutions cannot be found efficiently for large inputs
- Practical solutions rely on approximations, heuristics, or problem-specific structure
KEY TAKEAWAY: NP-Hard does not mean “impossible to solve” — it means “no efficient exact algorithm exists.” In practice, engineers accept approximate, near-optimal, or good-enough solutions.
For small $n$, exponential algorithms are feasible:
- TSP with 15 cities: \$14! \approx 87 \times 10^9$ — with pruning, solvable in seconds
- Scheduling 10 tasks: $2^{10} = 1024$ subsets — trivially searchable
Many real-world instances have structure that polynomial algorithms can exploit:
- Road networks are sparse and planar → efficient TSP heuristics work well
- Items in Knapsack may have special relationships → greedy or DP works for restricted cases
An approximation algorithm runs in polynomial time and guarantees a solution within some factor of optimal:
- TSP with triangle inequality: Christofides’ algorithm guarantees a tour ≤ 1.5× optimal
- Greedy graph colouring: May use more colours than optimal but is fast
Heuristic algorithms find good (not necessarily optimal) solutions quickly:
- Simulated annealing, genetic algorithms, hill climbing
- No optimality guarantee, but often perform well in practice
- “Good enough” solutions are acceptable in many business contexts
Many NP-Hard problems have fast algorithms for specific instances:
- Graph colouring for planar graphs (4-colour theorem)
- TSP for Euclidean distance (better approximations possible)
| Problem | NP-Hard? | Real-World Handling |
|---|---|---|
| Travelling Salesman (logistics routing) | Yes | Heuristics + approximation (GPS routing apps use greedy + local search) |
| Graph Colouring (exam scheduling) | Yes | Greedy heuristics (not always optimal) |
| 0-1 Knapsack (cargo loading) | Yes | DP exact solution (for small $n$); greedy for large $n$ |
| Job Scheduling (cloud computing) | Yes | Heuristics + approximation algorithms |
| Boolean Satisfiability (circuit design) | Yes | Modern SAT solvers (very effective despite NP-Completeness) |
Sometimes exact solutions are necessary (safety-critical systems, financial optimisation):
- Branch and bound: Systematically prune the search tree using bounds
- Integer Linear Programming: Specialised solvers (e.g., CPLEX, Gurobi) handle many practical instances efficiently
- Dynamic programming: Exact for pseudo-polynomial problems (e.g., Knapsack with integer weights)
If $P \neq NP$ (as widely believed):
- No polynomial-time exact algorithm will ever be found for NP-Hard problems
- The best we can do is heuristics, approximations, or exact algorithms for small/structured inputs
- Knowing a problem is NP-Hard justifies settling for a heuristic approach
EXAM TIP: When asked about the “feasibility” of an NP-Hard problem in real-world contexts, discuss: (1) input size, (2) whether approximate solutions are acceptable, (3) specific strategies used (heuristics, approximation, special-case algorithms).
