Hacker News
points by eru 3 days ago | 0 comments
> Perhaps this will be the push we need to finally, seriously consider the possibility that our formalisms of “efficient” and “efficiently verifiable” algorithms correspond to nothing resembling reality,

What do you mean? Do you mean that our heuristics shortcuts of treating P as efficiently solvable (and NP as efficiently verifiable) are not warranted? So far pretty much all algorithms in P that we found have small exponents. That hasn't changed, but it might change in the future.

Or do you mean something else?

Keep in mind that even most instances of many NP hard problems can be solved very efficiently in practice, because most instances ain't hard.

However we know problems that are expected to be 'easier' than NP that are hard to solve in practice. These are pretty much all the problems we build cryptography out of, because essentially these problems are in the intersection of NP and co-NP and that's expected to be smaller than NP. And cryptography has to be hard to break on average to work: a random key needs to be a good key.

> and P \in NP is actually ill-posed.

Oh, that's very simple to answer: P is not an element of NP. The question people care about is whether there's any element in NP that's not in P. In LaTeX notation P \subset NP vs P \subseteq NP.

I'm not sure what you mean by ill-posed? The question is very clear. What are you trying to say?

[–] antics 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"). 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.

[–] 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_...