Article

If Hard Problems Are Hard, Why Does Machine Learning Work?

14 October 2026

Some problems are believed to be hard to solve in general. Machine learning handles many practical instances of them successfully. There is no contradiction, and a simple map of the subject shows why.

A puzzle to start

A Sudoku is slow to solve and quick to check. Give someone a completed grid and they can confirm it in a minute; finding the answer from a partly filled grid can take an hour. Much of science and engineering feels the same way. A proof, or a delivery route that visits every city within a fixed distance, is hard to find and easy to check once found.

Computer science has a famous question about this gap. Can every problem whose answers are quick to check also be quickly solved? It is called P versus NP. Most experts believe the answer is no, but nobody has proved it.

Here is the puzzle. Theory shows that training even a tiny neural network to fit its data exactly belongs to the hardest class of these problems. Yet every day, machine learning trains networks with billions of adjustable settings, predicts the shapes of proteins and helps find proofs. At first glance, practice seems to contradict theory.

It does not. The theory and the applications ask different questions.

The map: four questions to keep separate

Figure 1. Four questions to keep separate. Each card says how the question bears on P versus NP and on machine learning.

P versus NP asks whether finding exact answers can always be as easy as checking them, for every input. Machine learning usually works with the inputs that actually occur, often accepts useful rather than exact answers and needs evidence as well as computing. Accepting an approximate answer can help, but some approximation problems remain hard in the worst case.

What P versus NP says

Strictly, P and NP classify yes-or-no questions, such as "Can this map be colored with three colors so that no neighbors match?" Finding an answer and answering such a question are closely tied, so I will keep speaking of finding and checking.

A problem is in P if it has an efficient method. Computer scientists call a method efficient when its running time grows no faster than a fixed power of the input size, such as the size squared or cubed. This describes how the work grows; it does not promise practical speed. A method whose time grows like the size to the tenth power is efficient in this sense and can still be impractical.
A problem is in NP if every yes answer comes with evidence, called a certificate, that is not too long and can be checked efficiently. A completed Sudoku grid is such a certificate. Sudoku is the familiar example, but the theory concerns puzzles whose grids can grow without limit, not the fixed collection of ordinary nine-by-nine grids.
Every problem in P is also in NP: if you can find an answer efficiently, you can check one. The question is whether NP contains anything beyond P.
Some problems in NP are the hardest of all. A fast method for any one of them would give fast methods for every problem in NP. These are called NP-complete. A problem at least as hard as every problem in NP, whether or not it is itself in NP, is called NP-hard; finding the best answer to an optimization problem is often NP-hard. The best known asks whether a long logical formula can be made true by some choice of true and false values for its variables; it is called SAT. Others include coloring a map with three colors and the delivery-route question above.

Why is SAT so central? Any efficient calculation, on inputs of a given length, can be written as a circuit of simple logic gates, and the circuit can be translated into a SAT formula. A fast method for SAT would therefore let us run efficient calculations backwards: given an output, find an input of the specified length that produces it, if one exists. That is what "P equals NP" would give us.

The consequences would be large. Most of today's encryption rests on calculations that are easy to run forward and believed hard to run backwards. If P equaled NP, that assumption would fail. How quickly codes would actually fall would depend on how fast the new methods were in practice.

Either P equals NP or it does not. The complexity theorist Avi Wigderson has pointed out a further possibility: the standard axioms of mathematics might be unable to settle which. Most experts expect P to differ from NP. Nobody has a proof.

This is a worst-case question, and it is easy to misread. Proving a problem NP-complete shows that a fast method for every input of that problem would give fast methods for all of NP. It does not show that no fast method exists. That is exactly the open question.

Worst case and typical case

So an NP-completeness proof says nothing about how hard typical inputs are. Real problems are often far easier than the worst case, and in several cases we can say why.

Industrial SAT problems. Modern SAT solvers routinely handle problems from chip design and software checking with millions of variables. Many industrial instances have structure that solvers exploit successfully, though some remain hard.
The simplex method. Linear programming, the mathematics of planning under constraints, can be solved in polynomial time by other methods. The simplex method, widely used in practice, can take an enormous number of steps on specially built inputs, yet it is fast on real problems. Spielman and Teng showed that a version of the simplex method has polynomial expected running time under a specified model of small random perturbations.
Sparse signals. Finding the solution of a set of equations with the fewest nonzero parts is NP-hard in general. But if the true signal has few enough nonzero parts and the measurements satisfy certain conditions, researchers have proved that an efficient method recovers it, approximately when the measurements are noisy. This result, called compressed sensing, is used in medical scanners.

For some of these successes, theory provides an explanation under specific assumptions. For industrial SAT, the explanation is still incomplete.

The neural network case: inputs, goals and design

In 1992 Blum and Rivest proved that one specific training problem is NP-complete: deciding whether a network of three simple threshold units, with a growing number of inputs, can fit all its labeled examples exactly. A fast method guaranteed to solve every instance of this problem would imply P equals NP. The result is not a theorem about all neural-network training.

Practical training usually seeks useful predictions on new examples, a different goal from fitting the training data exactly. It uses a chosen network design and does not promise success on every possible training set. The inputs also matter: photographs, sentences and protein sequences contain patterns that learning can exploit.

Why typical inputs are often easier

Natural data often contains patterns that learning algorithms can exploit. Photographs of faces vary in far fewer ways than random pixel patterns could. Sentences follow grammar and meaning. A trained network is, in effect, a compact description of the patterns in its data.

Structure is a promising explanation, not a sufficient one. A short description can exist and still be hard to find. Structure picks out families of inputs on which a method does well; it does not by itself guarantee that any efficient method will find it.

Proteins show both sides. In an idealized model that places a protein on a three-dimensional grid, even deciding whether a fold exists below a specified energy is NP-complete, so finding the lowest-energy fold is NP-hard. AlphaFold does not solve the general optimization problem in these simplified models. It predicts the structures of real proteins using patterns learned from biological data, and it does so with high accuracy. One possible reason is that evolution has favored proteins that fold reliably, so natural proteins may be far from the hardest cases. That is a hypothesis, not a result.

Evidence is a separate limit

Suppose P did equal NP. Would learning become easy? Not entirely, because learning faces a limit that has nothing to do with computing speed.

If several possible explanations fit the observations but predict different outcomes, faster computation alone cannot tell us which explanation is right. We need more evidence or additional assumptions. Compressed sensing makes this concrete: its guarantees need enough measurements as well as an efficient method.

Learning, search and verification

Some systems combine learned proposals with external checks. Formal mathematics provides a particularly clear example: a model proposes a proof, and a proof checker verifies it. AlphaProof, from Google DeepMind, proposes proofs in the formal language Lean, and Lean accepts only proofs that follow its rules. Here the check gives real assurance. This illustrates the gap between finding and checking: the system searches for a proof, and Lean independently verifies the result.

AlphaZero is a different case. It learned chess, shogi and Go by playing against itself, and a learned evaluation tells its search which moves to explore. That is learning guiding search. The evaluation makes the search far more efficient, but it does not certify that a move is best.

Neither system solves NP-complete problems in the worst case. Both make particular hard problems tractable more often.

The open question

We have theories that explain success under particular assumptions, but no general account of why today's methods work as well as they do across so many tasks. An important question remains: what makes the problems that occur in nature and practice easier than the worst case? In his 2025 Clay Research Conference lecture, Wigderson named understanding such natural inputs as a central challenge for complexity theory, and part of understanding how far AI will go. Among the natural problems he had in mind are the theorems mathematicians actually want to prove.

The map, completed

Figure 2. The map, completed. Each claim in the article, placed by the inputs it concerns and what counts as an answer. Proof checking sits below the grid because a checker applies its rules to any proof; the dashed border is the open question.