What's the alternative?

As I see it, the possible ways to think about it are as follows:

1) You must think of it as 50/50 possibility of being true until an absolute proof is found.

2) You look at places where it could fail, and if it passes then you update the likelihood based on that.

To me (and as this post argues) it makes sense to follow (2). Not only is it more useful practically (you can use that assumption to solve other things, conditional on it being true) but also it reflects the reality of the world. Even if it turns out not to be true in every case it is clear that in the majority of cases it is true.

Maybe it is untrue but it is possible to define the set of cases where it is untrue. If this is the case, it seems likely that class is very small, so it is mostly true. That is the opposite of a proof of course, but it does seem reasonable to think about your confidence of it being true as being somewhat proportional to the likely size of the class.

close complex border that seems to yield increasing numbers of "close calls" sounds exactly like the situation where there's a lurking, sparse class of "touches" that we haven't thought of

That's not really how it works though. If it keeps happening and those classes don't touch, then it typically means they aren't as close as they seem (ie, there is an extra dimension in which they are a long way apart). In this case it seems like the P/NP divide is actually a thing which means things which appear close actually aren't, so if you analyze them in that space they don't appear close together at all.

Any NP-complete problem reduces to any other, so if P=NP for any of them then it's true in general. Some more efficiently than others, of course.

I guess my only response would be that some of the complexity classes in "some more efficiently than others, of course" might be impractical even if they are theoretically possible.

Not really relevant here, though.

When we find a single bridge, all the complexity classes change, so we can only really divide the problems here into "ones we've found polynomial time solutions for" and "ones we haven't".

There may be something interesting about the ones we havent -- or we just didn't think of something obvious/a lot of special cases with high degree polynomials.

It's worth mentioning the near collisions happen in the low-dimensionality region of the border -- which doesn't have the same separating forecast, as it becomes easier to touch in higher dimensions. We can think of a sphere and a cube -- in low dimensions, a sphere lies inside of a cube; in higher dimensions, the surface bulges past the sides. You just don't see it until something like the 17th dimension. (Similarly, knot theory explodes with complexity in higher dimensions.)

Taking a "scientific approach" to asymptotic problems just makes the CS people advocating it seem vaguely hacky, since they're not even advancing a proper density argument -- it's just such a low-dimensional, poorly bounded argument that it's clear they didn't make a real calculation, they tried to dress up personal feelings in science.

Consider this. You have to bet on either P=NP or P≠NP. Where do you put your money. That is the question we are trying to answer.

His description of "passing tests" actually sounds like the buildup of stress before breakage, where many near-faults are generated.

I'm less confident of the resolution post reading that -- so it seems extremely weird to present as evidence that P != NP, as it shifted my beliefs the exact opposite way.

It's not even anything close: the gambler's fallacy requires that the events you're trying to relate are uncorrelated.

The logical structure of P vs NP is anything but uncorrelated along its surface, and a rough surface along the low-dimensionality region is a good indication of a rough surface along the higher-dimensionality regions.

So -- the fallacy requires you be trying to correlate uncorrelated things; I am not. I'm correlating things that are going to be correlated because of how the spaces are constructed.

Is it? This strikes me as pretty contentious.

Clearly there's a reason you think that isn't true -- perhaps you could share it instead of hiding behind just calling it "contentious".

It seems the stronger claim to suppose that the lower dimensions are rough and the top are smooth, especially when you think about where that roughness comes from.

Let's imagine a class "UP" which is the useful polynomial algorithms -- things we might actually compute.

The arguments raised here are a heuristic that UP != NP, which it certainly supports. My objection is that not only does that argument for UP != NP not support P != NP, it actually is evidence for P = NP, because UP seems to get asymtotically close to NP, and we know there are portions of P outside of UP -- suggesting we can find a "high" P region that sits atop UP and gets nudged over the line as UP approaches NP.

The suggestion that UP approaches NP but there's no P that crosses bears some supporting. Our disagreement seems to be over the obviousness of that relationship, and how much UP resembles P as a whole.

There are (apparantely) so many near misses for which it isn't clear why it should be a near miss. A great explanation for this near missing is the underlying fact that all NP problems contain some 'brute force' core that can never be polynomial.

Also note that the blog post does not at all concern your class UP. None of these are algorithms designed to be run. They are all about exploring abstract complexity classes.

You're correct that stormtroopers will never hit, wrong that stormtroopers are representative of the empire, and wrong about the correlation between stormtrooper hits and empire hits, because you're ignoring higher order effects (eg, while stormtroopers always miss, the empire must hit something to be the "bad guy" -- and they do: Luke's parents, Alderaan, Obi-Wan, Hoth, Luke's arm, etc.

But purely from the existence of stormtroopers consistently missing, you can infer there's a Darth Vader that must score some hits, or the plot wouldn't work. I think we might be in a similar case for P ?= NP, and you're all way too blasse predicting from stormtroopers.

Very little research has been done on P - UP, where UP is all polynomials with degree less than 10,000 and coefficients less than 10^100.

In fact, I don't know a single P-UP algorithm that wasn't explicitly constructed to be -- do you?

I just think most of us are subtly talking about UP, not P. (Including the blog post.) And that you've incorrectly inferred a "plot" when all you've observed is "redshirt fire".

You keep assuming we only look at UP, whereas actually our theoretical work explicitly looks at P. Often, we don't even care about actual efficiency of the algorithm. The constants might be astronomical, but we still like the algorithm for its asymptotic properties.

I'm not versed in recent research, but I imagine the composition argument above often leads to polynomial performance with stupid degrees. I expect people only compute the actual degree when they thing it might be low.

Again though, this is not my field of research.

I think it’s advisable to keep an open mind on the issue, and not simply on the actual question itself; it would not be surprising to me if the solution comes from something like adopting a different framework.

For example, time bounds and complexity classes smell a lot like conservation laws: “transforming such and such arrangement into such and such arrangement requires at least this much computation.”

That said, it’s possible (a) we’re currently failing to consider some “term”, (b) generally ignoring this term doesn’t cause problems when proving lower bounds but (c) the complex border and your “sparse touches” correspond to situations where the missing term plays a more significant role.

That’s a case where P probably isn’t equal to NP but keeping an open mind at least leads in more interesting directions, imho.

I also think people don’t take seriously the possibility of P being equal to NP but with intrinsically high degree. I say this not to be cute—“what if p is np but still de-facto intractable?”—but because I don’t think anyone has a great intuition for, say, what kinds of algorithms have polynomial solutions of minimum degree, say, 8...at least not in the same way we have good intuition for which algorithms are linear, nlogn, n^2, n^3, and so on.

It’s hard for me, at least, to feel overly confident in the “we’ve been working on finding a fast algorithm for seventy years and gotten nowhere” when our algorithmic intuition vis-a-vis higher polynomial degree seems so under-developed.

Even if you don’t consider it likely that p equals np, you can still follow this line of thought and consider the possibility that these “sparse touches” may be cases where the slippery problems like graph isomorphism (etc) correspond to problems with polynomial running times of (unexpectedly) high degree...and thus we keep finding these sparse touches along a seemingly-complex border because we don’t yet have a solid intuition for the capabilities of polynomial algorithms of high degree.

And so on and so forth. P probably isn’t NP but being dogmatic about it is neither fun nor interesting.

His argument seems to be "well, the border doesnt touch using under degree 100 polynomials, so it must never touch!"

I'm disinclined to believe that order 10^374738393874 polynomials can be accurately forecast by order under 100 polynomials, and suspect that portion of the border simply hasn't been examined at all or only in the most basic cases.

To summarize the argument in more general terms: the class of algorithms in P is those where you can derive some global property in terms of increment local decisions. For example, building the shortest path between two nodes in a graph can be done by always picking the closest node. By contrast, NP-hard algorithms have the problem that incremental local decisions don't let that happen: you might need to recolor an entire optimally-colored subgraph to admit a new node.

Furthermore, we know from research that there tends to be a very sharp transition from P to NP-hard in terms of transformation, where relaxing a single condition goes straight from P to NP-hard without any intermediate "we don't know where there is" space. This tends to suggest that it's not really so much a question of problems being P or NP, but rather of instances being intrinsically easy to hard.

The question of P=NP then is really about whether these hard instances are really exponentially hard, or can we embed them into a simpler instance using some combinatorial construct that merely makes it look exponentially hard. So it's still possible for P=NP, but the practical question of "will we get an efficient, guaranteed for all instances, solution to these problems?" is answered in the negative. When you do the combinatorial embeddings to make the polynomial time algorithms work, you end up getting constants that look like 3^2^2^4, and there's no way to shrink those constants to practical ones.

But it's absolutely insane to take the impossibility of low-constant, low-degree embedding as evidence as a general lack, given the rich structure of "large" numbers.

Which is what it's being used as in this post.

(On a side not, I love this kind of scientific approach to believing unproved theorems, and Polya has a lot of thoughts on the topic)