Thanks for the paper on the relation between edit distance in strings and SAT. I am very interested in the paper for a number of reasons.
It was related to this discussion because the problem can be related to DNA sequence comparison. (I forgot to mention earlier the well-known argument that you probably will not need to know everything about the biology of the brain in order to simulate the effective fundamentals of thinking any more than you need to be an expert in all details of computer electronics in order to be good at programming computers.) I had to look Frechet Distance up and after a few minutes I realized that I have spent some time thinking about the problem. However, I never made much progress on it. And I did not realize that edit distance of strings can be computed in quadratic time. I think my interest in string edit time was more AGI oriented because I was more interested in the problem of getting to one string (of concepts) to another (to a conclusion or an appropriate response) rather than trying to figure out the shortest "distance" that could have been taken if the conceptual relations were ignored. However, the shortest distance algorithms could be used to look for new relations and they could be used on the significant stepping stone stations in the train of thought. For example, if some additional criteria had to be accumulated then those criteria points could be considered as significant stepping stones. The vantage of the minimum distance could be used both to look for simple correlations or as a clue to relations that might be based on significant reasons. So I am very appreciative of the link to the paper. It will take me some time to figure it out. I am trying to intuitively figure out how string-edit distance could be related to SAT (since I cannot understand the paper yet) but I don't see how the near quadratic time for string-edit is related to exponential time for SAT yet. But it is making me think. Jim Bromer On Sat, Jun 27, 2015 at 7:24 PM, Matt Mahoney <[email protected]> wrote: > 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/24379807-653794b5 > Modify Your Subscription: https://www.listbox.com/member/?&; > Powered by Listbox: http://www.listbox.com ------------------------------------------- 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
