Markets are competitive if and only if P != NP

Title, setup, and prior work

• HN’s auto-title mangled “P ≠ NP” into “P = NP,” confusing the core claim.
• The paper builds on a 2010 result (“markets efficient iff P = NP”); together they imply markets cannot be both perfectly informationally efficient and perfectly competitive.
• Some commenters see that joint conclusion as elegant and intuitively plausible; others argue the earlier “efficiency ⇒ P = NP” result is shaky or mis-specified.

Assumptions about collusion and detection

• The model leans on a classic claim that the main obstacle to collusion is detecting defections (secret price cutting).
• Several participants dispute this: in many real markets rivals know they’re being undercut but lack any legal or practical way to punish, so power and institutional structure matter more than information.
• Others note that real, stable cartels exist, suggesting either the model’s “collusion unstable if detection is hard” result is too strong, or its assumptions don’t match reality.

AI, compute, and algorithmic collusion

• Some argue more compute lets firms simulate rich cooperative strategies and converge on collusive outcomes without explicit communication.
• Others see recent “algorithmic cartel” cases (e.g., rental pricing software) as ordinary cartels using algorithms as a fig leaf: key enablers were data pooling and human enforcement, not raw computation.
• Debate over whether AI meaningfully changes anything if everyone just follows the same pricing tool versus if heterogeneous agents run powerful, strategic models.

Complexity theory, P vs NP, and criticisms

• Several explanations of P, NP, NP-complete, and the P vs NP problem are provided for non-experts.
• Multiple commenters stress: NP-hardness or P≠NP says little about practical solvability with heuristics or near-optimal approximations.
• Some think the paper over-reads complexity theory (e.g., treating P=NP as “NP problems are easy in practice”), or should be framed more modestly as “general collusion detection is NP-complete.”
• A few see the whole line of work as stylized “spherical cows” with limited real-world bite; others find it conceptually illuminating but emphasize that empirical markets are messy, power-laden, and far from textbook assumptions.

Policy and “computational antitrust”

• The proposal that regulators treat market computational complexity as a safeguard against collusion is viewed as intriguing but normatively under-argued.
• One commenter invokes the is/ought gap: proving a mathematical property of models doesn’t by itself justify specific regulatory “oughts.”