I came across this paper on the Shtetl-Optimized blog that might be of interest to Jim Bromer. It proves that if there is an algorithm for computing edit distance in strings faster than O(n^2), then SETH is false, meaning there must be an algorithm for solving SAT faster than O(2^n). The paper is difficult. I only read the abstract. http://arxiv.org/pdf/1412.0348v2.pdf
SETH is the postulate that SAT is O(2^n), which is a stronger assertion than P != NP. If there is an algorithm for solving SAT in O(2^(n-e)) for some e > 0, then SAT would still not in P. But that is all the paper proves. Personally I would be surprised if such algorithms exist, either for edit distance or SAT. Here is the blog article. http://www.scottaaronson.com/blog/?p=2335 -- -- Matt Mahoney, [email protected] ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
