3 ms·
Cool, I did not know that SETH and PvNP were different
by bru_ 11y ago
Cool, I did not know that SETH and PvNP were different
- thomasahle 11y agoBasically: - If you can solve k-sat in time (2-eps)^n, you've refuted SETH. - If you can solve 3-sat in time (1+o(1))^n, you've refuted ETH. - If you can solve 3-sat in time n^O(1), you've refuted P!=NP. Since general k-sat is at least as hard as 3-sat, it follows that SETH is the strongest hypothesis (hence the name) and thus the most likely to fall. P!=NP is the weakest hypothesis and thus the most likely of the three to be true.
- darkmighty 11y agois (1+o(1)) essentially anything subexponential but hyperpolynomial?
- thomasahle 11y agoYeah anything subexponential. We can also write it as `2^o(n)`. It doesn't have to by hyperpolynomial, if you solve ETH in linear time, you also refute it :-)
- deleted 11y ago[deleted]