News for hackers. Stuff that matters.

A comment on Computer scientists prove that a 40-year-old algorithm is optimal. Parent comment

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.

[ Parent | on HN ]

There are no comments on this comment yet.