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.
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.
"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.
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.
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.
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.
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.
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.
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.
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.)
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.
Thanks for the correction! I updated my answer to fix that :)
"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.
oh that actually helps a lot. I was tying myself in knots trying to think it through.
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
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.
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.
1 reply →
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.
5 replies →
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
1 reply →
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.
Misunderstood your question sorry, I have no idea!
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.
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.
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)