points by triMichael 3 days ago | 0 comments
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
[–] 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.
(By the way, I think you mean NP-complete, not NP-hard. The Halting Problem is NP-hard.)