Hacker News
points by cochne 3 days ago | 0 comments
This is an amazing and unexpected result. To be clear though, it does not imply that NP is subexponential: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems admit subexponential time algorithms."

Edit: To explain more, it is guaranteed that you can reduce any NP problem to 3SAT in polynomial time with a polynomial factor in input size. You still have to solve it.

If 3SAT were solvable in polynomial time, then polynomial(polynomial(x)) = polynomial(x) and you're implied to have an overall polynomial time solution.

But what we have here is that 3SAT is solveable in subexponential time. subexponential(polynomial(x)) is not guaranteed to be sub-exponential.

Further edit: The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.

[–] marshray 3 days ago
> The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.

Wouldn't that also include functions that can be evaluated in hardware using a fixed number of gates? E.g., symmetric cryptography?

[–] pcbouman 3 days ago
A circuit with a fixed number of (binary logical) gates can be solved in constant time, as it will have a fixed number of input bits, so brute force will have a fixed number of input options to consider. This does apply to cryptographic algorithms with a fixed key size, like the ones used in practice, as well. The whole point of computational complexity is to look at the scaling behavior when you increase the inputs/key size/size of the circuit.
[–] ReptileMan 3 days ago
From my reading no. Because brute forcing anything symmetrical is already O(n). What protects us is the assumption that there is not enough energy in the observable universe to brute force 2^256 key.
[–] LPisGood 3 days ago
> To be clear though, it does not imply that NP is subexponential

Is there a subset of NP problems for which a subexponential algorithm would witness the entire NP class being subexponential?

[–] eli_gottlieb 3 days ago
~~Yeah, that's NP-complete problems.~~

EDIT: DISREGARD THAT I WAS MISTAKEN

[–] csheehan10 3 days ago
It's NP-complete problems if "subexponential" means O(2^{n^{\epsilon}}) for every \epsilon>0.

If subexponential just means 2^{o(n)}, (as it is here, O(2^{n/\sqrt{\log n}})), then no. E.g. if the cost of the reduction took you from n to \sqrt{\log n}n, then you'd be back to exponential time. The Subexponential Reduction Family is the class of problems that preserve subexponential time in the second sense.

[–] LPisGood 3 days ago
That is unfortunately not the case
[–] demibabs 3 days ago
Can you explain more?
[–] triMichael 3 days ago
After some back and forth with AI, I think I understand: 1. The Exponential Time Hypothesis being false shows that 3SAT specifically is sub-exponential time 2. Any NP complete problem can be changed into 3SAT in polynomial time

Put these two together and you would think that they would mean that any NP complete problem can be solved in sub-exponential time. But this isn't necessarily true because changing the NP complete problem into 3SAT can increase the number of variables, which can theoretically negate the sub-exponential time.

[–] demibabs 3 days ago
Oh ok, I understand what you mean.

(By the way, I think you mean NP-complete, not NP-hard. The Halting Problem is NP-hard.)

[–] edanm 3 days ago
The halting problem is NP hard, technically speaking, but it's much harder than that - it's uncomputable. I don't think it's common to refer to it as NP-hard because it's confusing.
[–] isaacfrond 2 days ago
Right. To be clear: the halting problem is not in the class NP. Any problem in NP can trivially be reduced to the halting problem and so the latter is NP-hard.
[–] triMichael 3 days ago
Thanks for the correction! I updated my answer to fix that :)
[–] bluepoint 1 day ago
I don’t know what you mean by negating the subexponential time. If the reduction is polynomial the time is still dominated by the 3SAT. Btw wikipedia says that the proposed algorithms correspond to 2^(n (log log n)^2/log n) which is subexponential but not in a practical way.

Edit: Ok, I a guess I am wrong if the reduction is n^ log n/(log log n)^2 we are back to exponential.

[–] bobmarleybiceps 3 days ago
oh that actually helps a lot. I was tying myself in knots trying to think it through.
[–] sourdecor 3 days ago
"Any NP complete problem can be changed into 3SAT in polynomial time" - if I remember correctly, turning an NP-complete problem into 3SAT is not part of the problem statement - it just means that when working with NP-complete problems, they are always translated to 3SAT first, and whenever someone is trying to prove something they are working against 3SAT.
[–] gbacon 2 days ago
The class NP-complete contains the hardest problems in NP. If you pick any problem in NP-complete, all problems in NP can be reduced to it (meaning that a solution to the problem you chose can be used to solve everything in the rest of NP) in polynomial time or “efficiently.” This applies to all of NP, including every other NP-complete problem, so in a sense, NP-complete problems are the same problem dressed in different clothing.

So the reduction to 3SAT could happen in principle, but it isn’t a necessary step.

[–] imadr 3 days ago
P=NP -> 3SAT has a polynomial time algorithm

P=/=NP -> 3SAT has no polynomial-time algorithm

ETH is true -> 3SAT has no subexponential time algorithm

ETH is false -> 3SAT has a subexponential time algorithm

------

ETH true -> P=/=NP

ETH false (!!!) -> P ?= NP remain unsolved

[–] demibabs 3 days ago
No I get that, but I don't get how proving 3SAT can be proved in subexponential time does not imply all NP-complete problems can be as well, since they can all be reduced to 3SAT in polynomial time.
[–] nightshade1511 3 days ago
Suppose 3SAT can be solved in 2^(n^0.9) time (this is not the actual bound in paper). And another NP problem can be reduced to 3SAT in polynomial time, but the reduction increases the problem size from n to n^2. Then after the reduction the other NP problem can solved in 2^(n^1.8) time, so it does not mean all np problems are sub exponential.
[–] raegis 3 days ago
Hey, this is a common error. (2^(n^0.9))^2 is not 2^(n^1.8) but 2^(2 * n^0.9).
[–] raegis 2 days ago
Apologies, I'm incorrect. I misread your math.
[–] Aunche 3 days ago
Suppose 3sat is solved in 2^sqrt(n). That's subexponential. An n^2 reduction from sat to 3sat is polynomial. However, an algorithm using this reduction with the discovered solution, would run in (2^sqrt(n))^2 which is just 2^n.
[–] stbede 3 days ago
(2^sqrt(n))^2 = 2^sqrt(n) * 2^sqrt(n) = 2^(sqrt(n) + sqrt(n)) = 2^(2 sqrt(n))

but

2^(sqrt(n)^2) = 2^n

[–] raegis 3 days ago
That last statement is not correct. (2^sqrt(n))^2 equals 2^(2 * sqrt(n)). If you just take n=1 in your expression you can see the error, your (2^sqrt(n))^2 yields 4, while 2^n is just 2.
[–] Dylan16807 3 days ago
Yeah but you're fixing the wrong thing. The problem after reduction to 3sat is (2^sqrt(n^2)). The altered n becomes the input to 3sat.

This also means your other comment here is wrong to suggest any error: https://news.ycombinator.com/item?id=50254142

[–] raegis 2 days ago
I was just correcting the statement as written. I see they meant to say something else. You are correct about my other comment--I was in a misdirected, math-correcting rage.
[–] jballanc 3 days ago
...that's...not how exponents work
[–] Dylan16807 3 days ago
The result is right, they wrote the parentheses in the wrong spot, don't be so shocked.
[–] caughtinthought 3 days ago
Basically 3SAT algo isn't sub-exponential enough to absorb the arbitrary poly cost for the reduction

So 3SAT+poly reduction ends up being exponential

[–] demibabs 3 days ago
Gotcha, thanks
[–] csheehan10 3 days ago
To achieve this you would need to show that 3SAT is solvable in 2^{n^c} time for every c>0, not just a single c<1.

In this case they have c = 1-0.5(\log \log n)/(\log n) which is approaching 1 for large n.

[–] imadr 3 days ago
Misunderstood your question sorry, I have no idea!
[–] vote_farisa_202 3 days ago
The algorithm's runtime is in faster growing than O(exp(n^a)) for any a < 1. It's not subexponential in the sense that factoring is, which I believe has a secondary exponent of 1/3 under the best algorithms.

It's still a big result, but it's mostly theoretical. It might help explain, structurally, why most SAT instances are far easier than an exponential model would indicate.

[–] calf 3 days ago
For example, a 2^√n subexponential algorithm then used on an input after a n^2 polynomial reduction from some other NP-complete language incurs a total running time of 2^√(n^2) = 2^n, which again is exponential.
[–] shoo 3 days ago
Yep! Or for a slightly generalised example, if we pick our sublinear function of n to be n^(1-epsilon) for some small epsilon > 0

then 2^(n^(1-epsilon)) belongs to 2^o(n)

Suppose p(n) is some polyonomial in n, our polynomial reduction. Let's make it a monomial for simplicity, p(n) = n^a

Does 2^(p(n)^(1-epsilon)) necessary belong to 2^o(n)?

No, that only holds if (n^a)^(1-epsilon) = n^(a (1-epsilon) ) < n^1 . So, it fails for p(n) = n^a for any a such that a >= 1/(1-epsilon)

[–] gewetensleegte 2 days ago
> To explain more, it is guaranteed that you can reduce any NP problem to 3SAT in polynomial time with a polynomial factor in input size.

No, subexponential is not the same as polynomial time. There's sub-exponential functions that grow faster than polynomial.