Markets are efficient if and only if P = NP (2010)

There is a reasonable-to-read paper [0] that explains everything; I will only share a few responses to your concerns.

"Our puny brains" have no problem constructing O(n^100) or similarly-ridiculous problems. Here is an informal survey [1] of several good examples. In my previous message, I indicated that matrix multiplication and CFG parsing are good examples; they are both cubic-time but we have come up with even cheaper algorithms for special cases, like sparse matrices or LR(k) grammars.

Whether P equals NP is not only a fundamental question, but it's the first of infinitely-many questions about the "polynomial hierarchy" or PH, a tower of ever-more-complex classes. And part of why the question is so important is that deciding whether P=NP is actually a problem in a higher rung of another complexity class further up in PH! P!=NP is like the first of an infinite family of very very difficult meta-proofs about complexity.

"RSA wouldn't break" because PRIMES is already known to be in P, via a famous paper titled "PRIMES is in P", and RSA keys are already sized to have impractical exponents.

What P=NP implies is much more powerful. First, let's consider the actual cost of a poly-time reduction. P is self-low, which means that P with a P oracle is equivalent to P. So if P=NP, then the cost of a poly-time reduction can be rolled in, and the entire problem is still in P.

Now, which problems would be transformable via P=NP? Well, we typically assume that the solution would include a poly-time reduction for 3SAT instances into some P-complete problem. Okay, great. However, we know that 3SAT can't be transformed opaquely; if this transformation exists, it must be able to examine and specialize the structure within each specific 3SAT instance. So we'd get one powerful theorem about logic (specifically, about SAT). But that wouldn't be the end.

We'd also get transformations for the following NP-complete problems, and each transformation would embody a free theorem about the nature of the structure of all instances of the problem ([2] for a bigger list):

* Graph theory: CLIQUE, HAMILTONIAN, K-COLORING (faster compilers!), COVER

* Number theory: TSP (faster packet routing!), KNAPSACK, SUBSET-SUM, PARTITION

* Formal systems: BOUNDED-POST-CORRESPONDENCE (holy shit, bounded Turing-complete analysis in P!?)

That's some serious free theorems! There's no reason to expect that whatever would give us so much stuff for free would be easy to prove. In fact, it's quite the opposite: The fact that any NP-complete problem, if it yielded, would give us deep insight into all of the others, should give us extreme pause before hoping that P=NP.

[0] https://www.scottaaronson.com/papers/pnp.pdf

[1] https://cs.stackexchange.com/questions/87073/what-are-the-ex...

[2] https://en.wikipedia.org/wiki/List_of_NP-complete_problems

Reading this comment thread is hilarious to a degree. I think that it really highlights how much noise gets thrown into a discussion when your naming becomes too relatable. Essentially bike shedding of theory discussion. If the Efficient Market Hypothesis has been called the “Fundamental Market Property Hypothesis M = H” or similar I doubt most would have made the comments they made. But because “efficient market” sounds to relatable most feel that they can comment without even knowing what the specifics of the EMH are.

It's not that it distorts the market, but it's one reason why the assumption that markets some how solve the principle agent problem in the first place is wrong.

My personal argument is that I don't believe markets solve either the principle agent problem or the economic calculation problem, and so to require them of other systems is hypocritical. But even if markets somehow do, then Turing completeness would strongly imply that there are other economic systems that also have those properties. Otherwise magic (which this paper is evidence against).

Thanks, very charitable reading but doesn't work because next sentence I said that the new prime is larger than largest. As other poster points out if 2,7 are all your primes you produce 15, whose primes are not larger than 7 so the "new prime" wasn't referring to one of them.

But that's not how I argued. Instead I showed that 15 is the new prime because it's relatively prime to all the primes. (By the assumption we had started from all the primes.) And this is what falsifies the assumption.

I think my argument is fine and I don't need to address whether 15 is really a prime.

Thanks for the explanation.

But, I do have some comments:

1)

As far as a I can tell the fact that PRIMES is in P doesn't mean breaking RSA is. The problem in rsa is integer factorization for which we do not know whether it is in P. (But also do not know for it to be NP-complete.)

But here you are actually supporting my point: event in that case we could choose sufficiently sized keys.

2)

And yes, the fact that P is self-low does seem to be the best justification we have to give such importance to P vs NP. That's also somewhat related to what I was saying about Turing machines and random access machines having polynomial reductions between them. But that's just because we decided to ignore polynomial reductions.

Continuing my example with even number being the same: We can see that multiplying an even number by any number yields an even number. Does that in any way justify ignoring the multiplication alltogether?

P with a P oracle really is equivalent to P, but O(n) with a O(n) oracle is not O(n), it's O(n^2).

3)

We have many NP-complete problems that have practical algorithms that perform fast on real-world inputs. I don't see how getting a free theorem about K-COLORING would practically mean faster compilers if the polynomial exponent was galactic.