Matt wrote: Anyway, my point is that decoding the human genome or natural language is n= ot as hard as breaking encryption. It cannot be because these systems are = incrementally updatable, unlike ciphers. This allows you to use search str= ategies that run in polynomial time. A key search requires exponential tim= e, or else the cipher is broken. Modeling language or the genome in O(n) t= ime or even O(n^2) time with n =3D 10^9 is much faster than brute force cry= ptanalysis in O(2^n) time with n =3D 128.
I don't know what you mean by incrementally updateable, but if you look up the literature on language learning, you will find that learning various sorts of relatively simple grammars from examples, or even if memory serves examples and queries, is NP-hard. Try looking for Dana Angluin's papers back in the 80's. If your claim is that evolution can not produce a 1-way function, that's crazy. ----- This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?list_id=303
