3 ms·
Am I reading this wrong? The title is wrong, right? The paper says that if a strongly sub-quadratic solution exists than the exponential time hypothesis (that
by ruggeri 11y ago
Am I reading this wrong? The title is wrong, right?
The paper says that if a strongly sub-quadratic solution exists than the exponential time hypothesis (that SAT cannot be solved in subexponential time) is invalidated.
That's very interesting, but it's not a proof that no strongly sub-quadratic solution exists for SED.
Note that exponential time hypothesis is strictly stronger than P!=NP. Even if SAT can't be solved in poly time, that doesn't mean it can't be solved in subexponential time. There are functions that lie between polynomial and exponential...
Of course, the paper was careful to explain it, but the media summary...
Edit: I was interested to learn about the notion of strongly quadratic; there are O(n^2/log n) solutions to SED, but this paper is casting doubt on solutions with time complexity O(n^(2-delta)) for any delta > 0. Another commenter mentioned a method to solve SED like this.
- ianamartin 11y ago"Prove" is an incredibly strong word. Too strong for this case.
- anonetal 11y agoI haven't seen too many results that rely on SETH, so just did a bit of research. Ryan Williams (from Stanford) at least doesn't believe SETH is true -- here is a nice talk by him on SETH: http://www.imsc.res.in/~vraman/exact/ryan.pdf http://www.imsc.res.in/~vraman/exact/ryan.pdf
- Sniffnoy 11y agoInteresting to note there slide 5 -- "For many polynomial time problems, improving the best known algorithms, even slightly, implies ¬SETH or ¬ETH." So apparently the edit-distance result discussed here is part of a history of similar results. Edit: More detail on this in slides 11 and forward.
- j2kun 11y agoIf you're going to be so specific you should also note that ETH and P != NP could be equivalent. So "strictly stronger" is also a hypothesis.
- Sniffnoy 11y agoNot just the exponential time hypothesis; the strong exponential time hypothesis. ETH is just the assumption that CNF-SAT requires exponential time, i.e., time 2^(cn) for some c; SETH is the assumption that it can't be done with c<1. Edit: Apparently n here refers to just the number of variables rather than the overall size of the problem instance. But that makes sense, because that's where the exponential dependence of the naïve algorithm is in the first place; adding more clauses just makes checking each possibility take slightly longer.