Hacker News
points by antics 3 days ago | 0 comments
"Ill-posed" here means that the formalisms we've chosen to represent "efficient" and "efficiently verifiable" algorithms could turn out to not correspond to anything humans would consider meaningful ("we posed the problem poorly"). For most people, a solution to an NP-complete problem that's barely-subexponential would be clear evidence of these formalisms being ill-posed.

There are many ways it might turn out to be ill-posed, this is just one of them. Impagliazzo's "5 worlds" survey is in some sense a catalog of some of these ways, and includes some of the ways you seem to be referencing (approxmations, probabilistic techniques, average-case efficiency; depending what you mean this could lie in the "Heuristica" world).

[–] eru 3 days ago
> "Ill-posed" here means that the formalisms we've chosen to represent "efficient" and "efficiently verifiable" algorithms could turn out to not correspond to anything humans would consider meaningful ("we posed the problem poorly").

OK, that's a reasonable worry and one that practitioners share. Thanks for explaining. Though I don't think ill-posed is a good term for this, the technical meaning of the term points in a different direction.

So far, as far as I can tell this new result gives much of any extra credence to that worry.

[–] antics 3 days ago
It is completely acceptable in math to use "ill-posed" to indicate that something is insufficiently specified, improperly formulated, or ambiguous. Math people do this all the time.
[–] eru 2 days ago
And that's fine. But here the question is perfectly well specified and properly formulated and not ambiguous at all.

The problem is that this formal question might not correspond to the informal question we actually care about.

[–] antics 2 days ago
You can hold that position if you like but you should do so knowing that the vast majority of people (including math people) would say that a formalism that classifies a technically-subexponential solution to an NP-complete problem as “efficient” is in fact improperly formulated, because the goal was specifically to formalize our intuition of efficiency. Our formulation in that case would have failed to do the single thing we laid out for it. Textbook improper formulation. There is not another way of putting this.
[–] calf 2 days ago
The technical result has nothing to do with "efficient" which according to textbook CS theory roughly defines it to be the set P, the strictly polynomial time algorithms. Has nothing to do with the ETH result which is still an exponential, 2^(n/ log n), just not a pure exponential.

I'm also confused what you are saying down here. Though I can see how "sub-exponential" is easily misleading terminology.

[–] antics 2 days ago
The point is not that ETH has anything to do with P or NP, but that the bounds theoretical CS chooses for its conjectures tend to be extremely round and convenient. Does reality actually prefer such nice, round bounds in general? Does reality prefer them in the case of P and NP?

In essentially all cases, we have no real reason to believe or disbelieve. We choose these bounds because we can't do better. It's often the case that we later prove them wrong with some extremely strange result. Here, we have weird bounds for 3-SAT, and a few weeks ago we had one for integer multiplication.

But this has also happened repeatedly throughout history. In the 50s Kolmogorov conjectured that n-bit integer multiplication was \Omega(n^2). Karatsuba produced O(n^{1.58}) during Kolmogorov's seminar on the topic. Strassen discovered matrix multiplication is O(n^{2.81}) while trying to prove it is O(n^3). And on and on and on.

Maybe P and NP are well-formulated and they do perfectly capture our intuition of "efficient" and "efficiently verifiable" algorithms. Or maybe they don't. We are probably going to keep finding extremely weird, cheesed-out bounds for famous problems, though. You can choose what you want to believe, but I think it would be more remarkable if the reality of P and NP turned out to be as clean as the bounds indicate.

[–] antics 2 days ago
Can't edit post, but here is a Berkeley prof who makes roughly the same point: https://bsky.app/profile/beenwrekt.bsky.social/post/3myuharu...
[–] calf 1 day ago
I don't agree with this narrative of the history.

It is true that CS had to make theoretical concessions. Just as Newton did. We don't criticize Newtonian mechanics (or, I don't know, Galileo?) for not being realistic about friction or idealized balls rolling down ramps. Their anti-empiricism was a starting point for physics.

To wit, the mathematical rationale for P-NP was precisely that that under polytime reduction this is still closed in P. That is a very reasonable starting point for a theory. This is also the reason why it is tripping up a large swath of the comment thread with people asking about subexponentials which do not preserve that closure

The opposite narrative is that in science, these idealizations yield profound intuitions and insights.

Furthermore, how far are you willing to go? Do you think Turing machines are invalid, that Turing-equivalent computation is pointless and unrealistic? So we are never allowed use that theory to convey the essential idea of in principle all computers being fundamentally functionally the same and that anything claimed to be more powerful than that had better have some incredible evidence, lest it be appeal to magic. Computability and complexity have a shared foundation so how much of that foundation are you going to reexamine?

Whereas if one wishes to be like a covert finitist/intuitionist, they ought to be open about that instead of accuse asymptotic complexity (or analgously, Turing computability as above) of trying to "cheese" complexity theory as a research programme. Meanwhile, it is true that P vs NP could have large exponents or constants in P, e.g. O(c*n^100...), literally this is the first thing taught in any complexity course or textbook. Students and practitioners remember this admonition well, maybe they just don't talk about it publicly as much.

One can go even further back. Cantor was marginalized for his ideas about infinities.

The difference with people like Lipton, and Knuth, is that the critique is coming from inside the house. In that they know the theory and the importance of it, but also hope/aspire for some new way to address the open question. They are keenly aware that P / NP is a problematic question, but not for lack of trying or stupidity on the part of other scientists. What is more likely is that the 21st/22nd century math to pose the better question does not exist yet (or may never be accessible to humans, another question well on the minds of many today).

Here's something to ponder. It is often observed that despite being NP-complete, many actual human instances are in fact tractable. E.g. routine airline scheduling depending on SAT solvers. But is this evidence that NP-completeness is a wrong theory or evidence that human-sized problems are a special case that becomes tractable (anthropocentrism), or some other more complicated reason?

[–] eru 1 day ago
Oh, I agree that it's improperly formulated (in that case), and that our terminological shortcut would fail. But I wouldn't call it ill-posed.

However, so far equating P with 'efficient in practice' seems to hold up.

[–] antics 1 day ago
I have said what I have to say about it. If you still don't believe me, you should consider reading the article "Is P=NP well posed?" from the eminent CS professor Dick Lipton https://link.springer.com/chapter/10.1007/978-1-4419-7155-5_...