[babypistol]

I have always been puzzled by why we as computer scientists give such importance to P vs NP. I always thought that even if P = NP the solutions might still be much harder (but only polynomially) to find than to verify. I always get angry when people say that P = NP would mean that problems would be equally as easy to solve as to verify. So, because of that, P v NP always seemed irrelevant to me.

But in the article, there is an interesting section on that:

> If P = NP, even with a high exponent on the polynomial, that means that checking strategies from the past becomes only polynomially harder as time passes and data is aggregated. But so long as the combined computational power of financial market participants continues to grow exponentially, either through population growth or technological advances, then there will always come a time when all past strategies can be quickly backtested by the then-prevailing amount of computational power. In short, so long as P = NP, the markets will ultimately be efficient, regardless of how high the exponent on the polynomial is; the only question is when, and the answer depends on the available computational power.

So this section, if I understand it correctly, says that problems in P are easy because the computational power in the world grows exponentially and we can assume that they will at least once become feasible to solve.

That's an interesting way of looking at it. Is this really the reason why we consider polynomial problems much easier than NP-hard ones?

[mannykannot]

It is important to bear in mind that this paper does not attempt to quantify how much market inefficiency results from not having polynomial-time solutions to the problems in NP, or how much different things would be if we did [1].

The importance of the difference between P and NP appears to be much greater in domains that are starkly discrete, such as cryptography, than in those that are approximately continuous, like finance, where there are often approximate methods in P that are very effective and efficient, at least for most real-world cases.

[1] Only in the last section does the author look at all at real market data, and there only to look for evidence in support of a weak prediction from the thesis. This is so riddled with uncontrolled factors that it tells us nothing about the quantitative consequences of N != NP on market efficiency.

[myWindoonn]

No. The reason why computation in P is considered tractable is because the exponents in polynomial coefficients in complexity analyses tend to be small. Linear-, quadratic-, and cubic-time algorithms dominate P, and we pride ourselves on finding ways to reduce those exponents. Some problems in P, like matrix multiplication and context-free parsing, have been analyzed to death this way.

We give importance to this question because it is open, it is big, it relates to many other parts of computer science, it has real-world implications, etc. The fact that you don't think this question is important likely means that you don't have the complexity-theoretic background required to appreciate the stark deepness of the question. This isn't bad, but it's myopic.

[babypistol]

Well I'm trying to understand why this question is big.

The fact that the exponents tend to be small in the algorithms that our puny brains were able to produce does not convince me one bit that all problems in P have algorithms with small exponents.

Why are you so sure that P vs NP is important? Does it really relate to so many parts of computer science?

I do agree that complexity analysis is a very (perhaps the most) important part of CS. But that does not necessarily mean that P vs NP is a fundamental question.

RSA wouldn't break even if P = NP. Even if we came up with a polynomial algorithm for integer factorisation in could have a much higher exponent than the multiplication required to verify the result.

This is what bothers me the most, people saying that P = NP implies that solving a problem is as difficult as verifying a solution. That's simply not true: P = NP implies that solving a problem is as difficult as verifying a solution (modulo polynomial reductions).

The part about ignoring polynomial reductions seems very important to me. Otherwise I could also say that: "all even numbers are the same", when I actually mean: "all even numbers are the same (modulo 2)".

Would you care to convince me why we chose to ignore polynomial reductions and not some other complexity class?

The best explanation I see is the fact that different Turing machine formulations (single-tape, multi-tape, one-way infinite, two-way infinite, ...) and also the random access machines have polynomial reductions between them. But even this does not justify the importance we give to P vs NP in my eyes.

[myWindoonn]

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

[babypistol]

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.

[myWindoonn]

Last reply; the sun's up and work starts soon. I'm leaving breadcrumbs.

On RSA: You're right, but this is only the tip of the iceberg. There's a concept, "Impagliazzo's five worlds," which explains in fine detail how the various P!=NP and P=NP scenarios impact cryptography. Basically, whether P equals NP could be an easier question than another open question, whether one-way functions even exist. There are cryptographic practical implications.

On multiplication: You are correct that DTIME(n) ≤ DTIME(n^2). However, P = DTIME(n) + DTIME(n^2) + DTIME(n^3) + …

If you would like to consider that only some small sections of P are tractable, then that's an understandable stance to take. There is, as I've mentioned before, an entire subfield of computer science dedicated to trying to move matrix multiplication from DTIME(n^3) to DTIME(n^2).

On approximation: Integer programming is simply harder than approximation. That's all. The fact that the approximations are tractable doesn't slake our thirst for the precise answers. Moreover, we don't know how BPP and NP relate yet, so it could be that there are ways to solve problems exactly in NP by randomized algorithms. We've found a few hints at this already, but derandomization is a hard process. (We don't even know if BPP=P, although P≤BPP and BPP is self-low. The holy grail of derandomization would be to derandomize BPP to P.)

Finally, I really encourage you to take a bit of time to read the Aaronson paper I previously linked, because it explains all this in much more detail. You are free to continue to think that the problem is not interesting, but I encourage you to at least get a sense of why it is hard.

[babypistol]

I don't understand why you are responding to me in such a condescending tone, but thanks anyway for the discussion.

I'm well aware that P vs NP is a very hard question (I have studied quite some complexity theory, although I am a bit rusty), I'm saying that it does not seem as fundamental (or interesting) to computer science as people believe it to be.

[leereeves]

That's assuming computational resources could grow forever without limit, which of course they can't.

[QML]

To add on: Moore's law is "dying", and that places further pressure on algorithms to get faster.

However, even in an exponential world, I am reminded of a quote:

"exponential algorithms make polynomially slow progress, while polynomial algorithms advance exponentially fast".

[babypistol]

Yeah, in this case we are back to square one and P vs NP again seems irrelevant to me.

[pbhjpbhj]

Isn't finding the optimised solutions to market transactions something that is part of the market too?

So, not only do you have the resource problem highlighted in sibling posts but also a recursion problem:

Vis, when the problem becomes solvable the optimisation must add the market transactions for the sale of resources to solve the optimisation, so now one needs to optimise that larger problem ... which again involves transactions, which shift the original optimisation.

If you can predict the optimisational perturbations needed to solve the enlarged system, then you might be able to break the cycle .. but won't you need to transact the processing of the perturbation, the optimisations of which will shift the inner optimisation.

The solution itself would be marketable, perturbing the market and negating the optimisation?

My instinct may be wrong but it suggests the market can't be [perfectly] optimised (but in practise that probably doesn't matter).

Optimising markets might be the extent goal of capitalism, but it's not the extent goal of the rich (in general) who would rather remain rich than have perfect allocation of resources.