P = problems solvable in polynomial time. NP = problems whose solutions are verifiable in polynomial time. The question is open, but widely believed to be .
Key classes:
- P — efficiently solvable (sorting, shortest path, linear programming)
- NP — efficiently verifiable (SAT, graph coloring, traveling salesman)
- NP-hard — at least as hard as every NP problem. May not even be in NP
- NP-complete — in NP AND NP-hard. The "hardest" problems in NP (SAT, 3-coloring, subset sum)
What this means for ML:
- Many ML problems are NP-hard — optimal feature selection, optimal neural architecture, optimal clustering (k-means), finding the global minimum of a non-convex loss
- We use approximations everywhere — SGD doesn't find the global optimum; it finds a good-enough local one. K-means uses Lloyd's algorithm (local search). This is the pragmatic response to intractability
- regularization (exact sparsity) is NP-hard → we use as a convex relaxation
- Training a 2-layer ReLU network to global optimality is NP-hard — but SGD works in practice due to overparameterization and loss landscape structure
- Inference in general graphical models is NP-hard → variational inference, MCMC
- Structure learning (finding the optimal Bayesian network) is NP-hard
Reductions — proving problem A is at least as hard as problem B by showing B can be transformed into A in polynomial time. This is how NP-completeness proofs work and why recognizing a problem's complexity class saves you from attempting exact solutions.
Practical takeaway: when an ML problem is NP-hard, don't search for exact algorithms — design good approximations and understand their guarantees.
See also: Big-O and Complexity Analysis, Convexity