Markets can be informationally efficient or competitive, but not both. This is not a policy tradeoff — it is a computational one.
Duffy (arXiv:2602.20415) proves that competitive market outcomes require computational intractability. Specifically: markets are competitive if and only if P ≠ NP. The mechanism is collusion detection. If P = NP, firms can efficiently verify whether all cartel members are honoring the agreement — checking deviations in complex multi-good markets becomes polynomial. Sustainable collusion requires monitoring, and monitoring requires solving NP-hard problems. When those problems become tractable, cartels stabilize.
The converse: if P ≠ NP, firms cannot efficiently detect deviations from collusive agreements in sufficiently complex markets. The cartel cannot police itself. Defection goes undetected, trust erodes, and the market reverts to competition. The complexity of the market is the enforcement mechanism — it is computationally too expensive to collude.
Combined with prior results showing that informationally efficient markets (where prices reflect all available information) require solving NP-hard problems, the impossibility emerges: efficiency requires tractability (P = NP) and competition requires intractability (P ≠ NP). You cannot have both.
The paper notes that AI is expanding effective computational capacity toward the tractable regime — not by proving P = NP, but by making NP-hard instances approximately solvable at relevant scales. This predicts algorithmic collusion: not through explicit coordination, but through enhanced monitoring capacity that stabilizes implicit agreements. The collusion is computational, not conspiratorial.
The general observation: when a desirable systemic property (competition) depends on agents' inability to solve certain problems, expanding computational capacity can destroy the property it was meant to improve. The market's health depends not on the rationality of its participants but on their bounded rationality. Remove the bound, lose the health.