> Intuitively, almost everyone assumes that P != NP

Donald Knuth believes P = NP.

Source: http://www.informit.com/articles/article.aspx?p=2213858&WT.m... (question 17). Also cf. https://www.quora.com/Why-does-Donald-Knuth-think-that-P-NP

But keep in mind that he (and just about everyone who believes P = NP) thinks any proof of it will be non-constructive and that we will never actually find a polynomial-time algorithm for NP problems.

Is that really true though? What if someone solves does P equal NP problem by finding a polynomial time algorithm for a problem in NP, but the asymptotic run time is O(n^10^100)?

Sure the race would be on to improve that, but in the meanwhile no difficult problems would become solvable.

related to https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...

That was really entertaining, thanks for linking it.

I especially liked this bit:

David Johnson famously once said, For any instance {G = (V, E)} that one could fit into the known universe, one would easily prefer {|V |^{70}} to even constant time, if that constant had to be one of Robertson and Seymour’s.

I was curious so I tracked down this:

Johnson estimated that the hidden constant is “somewhat larger” than 2 ⇑ (2 ⇑ (2 ⇑ (h/2)) + 3), where 2 ⇑ t denotes an exponential tower of t 2s (2 ⇑ 0 = 1 and 2 ⇑ t = 2^2⇑(t−1)) and h is the number of vertices in H.

It's generally not the case though: problems that arise 'naturally', i.e have not been constructed to counter my forthcoming point, in P seem to be of low order.

If NPC problems where P in n^{10^100}, wouldn't we expect a wealth of problems between there and the myriad at n^2 or so?

Why would that be more surprising than the fact that some "natural" problems are polynomial and some are exponential, given that an exponential running time is asymptotically slower than any polynomial running time?

Often, just knowing that something is possible can be a catalyst for big advances.

It's easier to get people to devote resources to a hard but solvable problem than to one which may not even be solvable.

This interpretation is wrong. The class P contains for example O(N^(10^100000!)), that are not "solvable" by any remotely reasonable meaning of the word.

This is true, but it's difficult to imagine what such a problem could look like. In reality, algorithms tend to come in discrete complexity "units" with very small terms. A linear algorithm isn't just fast -- it tells you something about how such an algorithm works and thus something important about the problem it solves. A quadratic algorithm can be interpreted as a "considers all pairs from the inputs" algorithm. An n*log(n) algorithm does a divide and conquer step for each input. Moving to the exponential world, you have the 2^n "tries all combinations" and n! "tries all orderings" type algorithms, which again, make sense both as mathematical functions as well as behaviors that constitute sensible algorithms.

What does an O(n^10,000) algorithm do? What understandable problem yields a solution that behaves that way?

To follow up on this, in computational linguistics, there is a sharp divide between facts which take cubic time, like recognizing whether a string belongs to a context-free language, and facts which are halting-problem-hard, like recognizing whether two context-free grammars describe the same language. There doesn't appear to be much of a middle ground.

In another realm of computational mathematics, matrix mjultiplication is cubic, with optimizations that can approach quadratic time with lots of effort. It's conjectured that matrix multiplication can actually be brought arbitrarily close to quadratic time, but at the expense of ever-more-complex algorithms.

It could very well be that the biggest interesting exponent in P is 3 or 4.

The AKS algorithm has been reduced to an exponent of 6. That really strikes me as large for polynomial time algorithms though.

The coupled cluster method CCSD(T), considered the "gold standard" of quantum chemistry, is O(N^7). That's the highest-exponent polynomial time algorithm I'm personally aware of that sees regular use. The various coupled-cluster variants are all basically approximations to full configuration interaction, which is a much worse O(N!).

It is! At first, the following may appear quite counter-intuitive, but if you think about larger N and the fact that you often want efficient algorithms also when processing large amounts of data, it becomes clear that an exponent of 2 or 3 is, in practice, often the most we can realistically handle even when the problem is in P, and even though O(n^2) is extremely low from a computational complexity perspective.

For example, when you have an O(n^3) algorithm and want to process 10,000 elements (which are very few in many situations), it will be, as a rough estimate, 1,000,000,000,000 times slower than processing a single element. This will be acceptable only in very specific situations. As a rule of thumb, an exponent of 2 is already unacceptably slow in many practical situations, and at least on the verge of being unacceptable in others.

That explains why we don't have widely implemented algorithms of higher-degree polynomial complexity, but it doesn't explain why we haven't thought of many such polynomial algorithms that just aren't practical. After all, we can easily name lots of super-exponential algorithms. They're not directly useful for even moderately sized data, but they arise naturally from looking at certain types of problems, so we almost can't help but find them. The same doesn't seem to be true for polynomial algorithms with high degree.

You're essentially referring to the idea that could be loads of high-order poly-time algorithms, but we ignore them because those algorithms are slow, and therefore we don't use them. So in the space of all useful algorithms, we simply have a very biased sample.

I think the truth is more profound than that. There actually don't exist very many interesting* algorithms in the classes O(n^(k>3)). The real world we live in and model does not feature many interesting problems for which high-order polynomial complexity algorithms are natural solutions.

*Not sure what the right word to use here is...maybe non-trivial? The point I'm going for is to say that obviously we can invent an O(n^5) algorithm by simply nesting our loops five-deep and printing something, but that's a constructed example. I'm looking for algorithms that naturally arise as a solution to some problem.

For example, there is 0.8776-approximation that runs in about O(n^{10^100}) https://arxiv.org/abs/1205.0458v2 There are also a lot of graph problems like "distinguish 3-colorable graph from graph that can't be colored in 3 colors even after removing eps part of edges" with large polynomials (IIRC, we got something like O(n^{2^40000}) when tried to find degree explicitly).

While not strictly in the same vein as O(n^10k), the constant factor in the proof that L=SL is 3^(2^65536) at the smallest. A lot of combinatorial problems can generate such algorithms, since they tend to rely on "we can solve this problem if this condition holds, we can make this condition hold for all inputs if we blow up our input with this large structure [which is technically constant time since the structure is fixed and not variant on size!]." Consider that this is the field of mathematics that produced a number that is "3 raised to itself so many times that I need to describe an algorithm just to write that number" that was used as the upper bound to a solution (the lower bound of which was 6).

Your observation about correspondence between algorithmic complexity and its structure seems very interesting to me, thanks for sharing.