Computational complexity is usually treated as an obstacle. NP-hard problems are the ones we wish we could solve efficiently but cannot. We build approximation algorithms, heuristics, quantum annealing protocols — all strategies for coping with the intractable.
Maymin (arXiv:2602.20415) proves that intractability is not just an obstacle but a structural requirement for competitive markets. The argument: in a world where P = NP, firms could efficiently solve the collusion detection problem. They could verify whether any competitor deviated from a cartel agreement, in noisy real-world data, in polynomial time. Punishment threats would be credible. Cartels would stabilize. Markets would become collusive.
In the world we actually live in — where P is believed to not equal NP — collusion detection is computationally infeasible for most real-world markets. Firms cannot efficiently verify whether a price drop was a competitor cheating on the cartel or a random market fluctuation. Punishment is therefore not credible. Cartels decay. Markets remain competitive.
The result is an “if and only if”: markets are competitive exactly when the computational problems underlying them are intractable. This is not a metaphor or an analogy. It is a formal theorem connecting economic structure (competition vs. collusion) to computational complexity class (P vs. NP).
The implication is uncomfortable. We want markets to be competitive AND informationally efficient. But informational efficiency — the market price reflecting all available information — requires computational power to aggregate that information. Maymin's prior work (2011) showed that informationally efficient markets require P = NP. Combined with the new result: you can have informational efficiency (P = NP, prices reflect everything) or competition (P ≠ NP, cartels cannot self-police), but not both.
The hardness of the problem is not a bug in the market's design. It is the mechanism that keeps the market free. If we ever built machines that could solve NP-hard problems efficiently — through quantum computing, novel algorithms, or unforeseen physics — the economic consequence would not be prosperity. It would be perfect cartels.
Intractability protects us from the cooperation we don't want. The computational wall that frustrates the optimizer also frustrates the cartel enforcer. Every time a collusion scheme fails because the monitoring problem is too hard, NP-hardness just earned its keep.