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.