Re:Computer scientists prove that a 40-year-old algorithm is...
by anonetal on Thursday June 11, 2015 @12:25PM
(#9700617)
I 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
Re:Computer scientists prove that a 40-year-old algorithm is...
by Sniffnoy on Thursday June 11, 2015 @07:27PM
(#9703093)
Interesting 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.
Re:Computer scientists prove that a 40-year-old algorithm is...
by Sniffnoy on Thursday June 11, 2015 @07:10PM
(#9703038)
Not 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.
Re:Computer scientists prove that a 40-year-old algorithm is...
by j2kun on Thursday June 11, 2015 @03:50PM
(#9701894)
If 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.
Re:Computer scientists prove that a 40-year-old algorithm is...
by ianamartin on Thursday June 11, 2015 @02:52PM
(#9701532)
"Prove" is an incredibly strong word. Too strong for this case.
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.