The implications are not significant..? the real world is messy enough that this will not ever apply.

So it pulls exclamation marks. . .angle brackets maybe?

    “=“ <> “!=“

For the older among us, that's .ne.

assuming the typical "spherical market in a vacuum where the agents are maximally rational non-biological utility maximizers"

In a P=NP world, it still takes only one uninformed participant to make the market inefficient. I don't think the implication is bidirectionally true unless you assume every single player is rational, infinitely smart, and has access to the same set of information.

So markets can only be (perfectly) efficient or competitive, not both at the same time. Largely theoretical but it tracks common sense!

Assuming the original result is correct, isn’t the linked paper simply a corollary?

Yeah, the most obvious recent example of this is RealPage’s YieldStar product. It advised property managers on what they should set their rental rates to, and allegedly established a cartel in which RealPage’s customers coordinated in pricing their units.

YieldStar was technically an “AI” product, but I don’t really think the computational abilities were what enabled the collusion. RealPage’s employees (according to the DoJ[0]) would actively monitor whether companies were following their pricing recommendations and call up companies that defected. And the software itself used dark patterns to make it easier to simply follow the YieldStar pricing suggestions, rather than set a lower rental rate and be more competitive. The algorithmic pricing I think did allow people to launder their own judgement and simple “trust the process” in a way that in the past would have required knowing complicity with the cartel, but I don’t think it required substantial compute capacity.

(This isn’t a comment on the paper by the way, which I glanced at but did not have the background knowledge to fully comprehend)

[0] See the section labeled “RealPage Uses Multiple Mechanisms To Increase Compliance With Price Recommendations” https://www.federalregister.gov/documents/2026/01/21/2026-01...

HN is competitive if and only if != != =

The actual paper’s title is

“Markets are competitive if and only if P ≠ NP”

It’s 2026, people, you don't have to use crude ASCII approximations of mathematical symbols any more.

> Seems that HN's auto-headline rewriting in this case has made a critical error :)

I'm eagerly awaiting the day someone proves that P != NP and HN edits the title of the announcement post in this exact same way.

The paper seems to be based on an invalid assumption. From the abstract:

> If P != NP, the collusion detection problem is computationally infeasible for markets satisfying a natural instance-hardness condition on their demand structure, rendering punishment threats non-credible and collusion unstable.

...and then from the paper:

> Stigler (1964) famously argued that the “chief difficulty” of collusion is detecting “secret price-cutting.”

The thing is that Stigler's insight is far from proven, and indeed, the primary difficulty in collusion is often not the detection of defection. Firms know they're being undercut all the time. The problem is that very often, there is nothing they can do about it. Markets are specifically structured as firm-to-firm transactions, where competing firms have no leverage over what your firm can do or what sort of transactions you can conduct, and as long as this condition holds it doesn't matter if you know that a competitor is fucking you over, you can't do anything about it.

I'd argue that the increase in collusion and anticompetitive behavior lately is because these conditions increasingly don't hold. When you intersperse another party in the transaction, eg. a regulatory agency, permitting body, or exclusive distribution deal, you introduce a leverage point for incumbents to punish competitors who choose to undercut them.

> I don't see how this follows, except in the most straightforward way.

A more capable actor can anticipate the actions of other participants to a greater degree. Imagine that all sellers are such actors. Consider that collusion happens (and is bad) because it enables sellers to extract much higher prices than the market would otherwise set. When all sellers are such "hyper rational" actors they can act cooperatively to maximize their profits without the need to explicitly coordinate in secret. The same end result without the illegal step sure feels like an end run around the spirit of the law.

> Edit: Isn't another implication of this, that increased compute -> collusion imply that increased compute -> communism becomes feasible?

That depends on what you think the problem that communism faced was. AI increases our ability to centrally plan but it probably doesn't do much in and of itself to combat various forms of corruption. Human greed is an invariant; by glorifying and directly making use of it capitalism is hardened against a number of otherwise pathological behaviors.

HN materially changed the title to something surprising!

or maybe compute allows simulating a lot of possible cooperation strategies, and arriving at the one maximizing profits for the colluding parties

Defi does a pretty good job regarding unimpeded access in comparison to the more traditional venues. This isn’t just about getting money into the system, but also what instruments you have access to.

The term ‘perfect information’ is a bit of a mirage, and has been shown to be impossible in physics (uncertainty principle).

What really matters is information advantage: Does your inexact expected value function consistently beat others’ calculations in the market. Here, the true value - value really is just a word and is dependent on people - is irrelevant.

But you can just give computers to each of those millions of people and propagate the information, instead of having less reliable humans doing it? That's kind of what's already happening.

> while P != NP

You don't know that!

In a minute you'll be tellin' folks that those quantum fangdoodles aren't going to revolutionise their stock pickin'!

You do realise that you'll never work in this town again? \s :)

Not quite sure what you're suggesting here; perhaps it's satire?

If P!=NP then it is arbitrarily smaller, for the same reason that e^x > Cx^N for any constants C and N, as long as x grows big enough. There is no epsilon in that can overcome that, no matter how big you make it, because x will eventually dominate the equation.

There are a lot of cases where pragmatically x remains small enough that it doesn't matter, and a P algorithm will give you an answer more quickly. (For the same reason I only ever write bubble sorts: I would only write my own at all if I knew that the list would never be bigger than 10. Even then it's only when using the library is too much trouble for some reason.)

But we care about P and NP when the number can potentially be very, very large.

Which would in turn imply that markets cannot be simultaneously efficient and competitive.

Right. Maybe a better and more humble title is "Identifying General Instances of Market Collusion is NP-complete". Not as headline grabbing, but more in line with the actual result.

next stage - a single AI which computes the "correct" price that everyone else agrees on, and instantly reprice all financial instruments without trading them, thus not paying transaction costs

I hate to make the worn out AI to RNG comparison, but this kind of simultaneous "collusion" is really like assuming that everyone is using the same RNG seed to make their calls.

Sounds like soviet communist Sci-Fi with a planned economy managed objectively by The Computer.

It’s a great excuse for collusion

> just that they are sufficiently efficient that beating them is a genuinely hard job requiring heavy, expensive analysis

No expensive analysis is needed. Beating them just requires (1) having disproportionate capital to others, and (2) having disproportionate control (and therefore know in advance) whatever the markets are pricing.

It helps that there are enough believers (in the religious/cult sense) that markets are 100% efficient, that they will deny that any of that is happening - even while they lose their shirts to those who are doing the market manipulation.

NP factorial sounds like NP-ultra-hard.

It builds on a similar paper from 2011 by the same author, though. They've just found something very specific that they enjoy analyzing.

P and NP are classes of computational problems.

A problem in P can be solved in polynomial time - the computation required grows relatively slowly as the input size increases. Like sorting a list of numbers.

A problem in NP requires exponential time or greater, but a proposed solution can be verified quickly. For example, checking a completed Sudoku puzzle.

It is believed but unproven that all problems in NP are NOT in P.

It's a vast generalization of the cost to verify a problem/solution.

- P means polynomial - NP means nondeterministic polynomial

Roughly polynomial (P) represents the upper bound of the cost to verify, and the polynomial characterization says that given a problem with a certain input (e.g. the input can be the number of training examples in ML training set or the number of constraints/conditions in a general problem— e.g. all the places you want to visit on your next trip, given many "wants" in a group)

When the cost is polynomial relative to the input size it means it can only be finitely larger than the input - that's a characteristic of the polynomial which is just a finite sum of powers of x (the input).

When the cost is nondeterministic polynomial, one way to think about it in what is called a nondeterministic Turing machine. The nondeterministic part refers to the "states" that the machines can transition to from any current state. When the transition can happen to more than one state, we say it's non-deterministic— and can imagine it's determined by some probability.

The general assumption is that polynomial (P) is easier than nondeterministic polnomial (NP). This isn't necessarily the case as there can be arbitrarily large finite numbers (making P solutions intractible)

The P vs NP problem is one of the main open problems and generally considered a crank magnet and general confusion. For a good (likely the best) resource see https://scottaaronson.blog/

I have taken algorithms courses.

This video explains in detail: https://www.youtube.com/watch?v=YX40hbAHx3s

In short, P means Polynomial time (i.e. markets can solve computation problems efficiently) and NP means Non-Deterministic Polynomial time (i.e. markets can verify solutions of computation problems efficiently but solutions are found by luck).

If P != NP, it means luck CANNOT be engineered and markets are competitive.

Wikipedia is a good source on this

P complexity class

https://en.wikipedia.org/wiki/P_(complexity)

NP complexity class

https://en.wikipedia.org/wiki/NP_(complexity)

P vs NP question

https://en.wikipedia.org/wiki/P_versus_NP_problem

well obviously N=1

in CS we define a complexity class as a set of problems that have the same growth characteristic. that is for a problem size N, how long does it take in the worst case to find the solution for that problem.

one such class is the Polynomial class, or P, where the time to solution is some fixed exponent of N (like N^2, or 3).

the next big step is NP, which require a polynomial number of nondeterministic steps, whose solution can only be verified in polynomial time. usually solutions to NP problems are exponential in cost with respect to N (like 2^N), but thats not part of their definition.

problems in NP are generally identified by mapping them into a well known problem known to be in NP, where the mapping has to occur in polynomial time.

its an open question as to whether NP as a class can actually be solved in P time, but most people doubt that that is really the case.

That seems to stretch the meaning of market inefficiency. Is the lack of unlimited free energy an inefficiency in a market? Because an entrepreneur who achieves that is going to do pretty well. I’d say that would be creating value not optimizing market efficiency.

In perfectly efficient markets, arbitrage gets paid exactly as much as it costs to discover and execute the arbitrage. Entrepreneurs would still exist, they would just be ambivalent between finding new arbitrage opportunities and seeking market-rate employment for their skills in finding arbitrage.

Seems like t is a very critical variable then. For example, you could imagine a particular market is "perfectly" efficient at the moment (however you want to define the boundaries of a particular market), and there is no opportunity. But then a completely unrelated company or university makes a fundemental advancement in materials science that fundamentally changes the landscape. An exogenous shock in other words.

In a certain sense I guess this is why every anti-trust suit fundamentally comes down to defining the market bubble more than anything else.

Ok so the market is perfect... but I exist and have labor to provide. Am I not naturally an "inefficiency" by not participating in the market? Therefore by participating alone, I have a new wrinkle to work from?

Yet neither paper seems to eliminate the case of markets being neither. So both titles are incorrect.

Except Maymin 2011 fails to even establish that his narrow definition of "markets are efficient" (specifically, finding a profitable technical analysis) is actually in NP.

Why? Don't you prefer getting better prices when you want to go buy a stock?

Game theory here is applied to two fundamental market theorems. It’s a way to analyze the validity of those assumptions, rather than to build a new model. Empirical evidence to the contrary is expected given mutually inconsistent premises, which is what the author’s results predict. The author has simply used game theory math to disprove economist math.

I suspect this is a standard mathematical “it is computationally impossible to do this in the general case despite it being entirely feasible in many cases”.

Or maybe the markets are actually proof that P = NP :^)

Or, P=NP