Hacker News
points by jltsiren 3 days ago | 0 comments
It's been a long time since I seriously thought about complexity theory, but I'd say no. For similar reasons to why complexity class E is not closed under polynomial-time reductions.

The most important component in the time bound is of the form 2^{n / polylog(n)}, which is subexponential. But if you have reduction from another problem that increases instance size quadratically, the algorithm for the other problem is no longer subexponential. Which means we are still essentially in the same neighborhood as before.

It's a huge result if true, and probably the first major AI result that affects the papers I read. But since the boundary in the hypothesis was kind of arbitrary, breaching it should not significantly change our intuition on complexity classes.

[–] hakuseki 3 days ago
I think the bigger issue (for someone hoping for P=NP) is that there's a huge gap between "polynomial" and "exponential." Even if it were the case that all NP problem classes had subexponential decision algorithms, that would not get us close to P=NP.
[–] cwillu 3 days ago
How much effort has been expended on optimizing those reductions though? I have a harder time believing that one can hang one's belief in P!=NP on that particular hook.
[–] rao-v 3 days ago
There are so many just barely sub-exponential function shapes between 2^(n / sqrt ln n) {this result} and 2^(log n) {polynomial time}!
[–] jltsiren 3 days ago
The challenge is the initial reduction from an arbitrary problem in NP to the problem you want to prove NP-complete.

In the usual approach, you assume a nondeterministic Turing machine (or equivalent) that solves the problem and a time bound (which can be an arbitrarily large polynomial). You then create a boolean expression that can be satisfied if and only if the Turing machine accepts the original problem instance. Unfortunately all constructions so far have included the time bound as a factor of the size of the expression.