On 2/21/08, Ben Goertzel <[EMAIL PROTECTED]> wrote: > On Wed, Feb 20, 2008 at 4:27 PM, J Storrs Hall, PhD <[EMAIL PROTECTED]> wrote: > > OK, imagine a lifetime's experience is a billion symbol-occurences. Imagine > > you have a heuristic that takes the problem down from NP-complete (which it > > almost certainly is) to a linear system, so there is an N^3 algorithm for > > solving it. We're talking order 1e27 ops. > > That's kind of specious, since modern SAT and SMT solvers can solve many > realistic instances of NP-complete problems for large n, surprisingly quickly... > > and without linearizing anything...
Comparing the problem at hand with SAT may not be very accurate. First, we need to formulate the problem more clearly -- what exactly are we trying to do. Then we can estimate whether it's feasible with available computing power. Also, modern complexity theory has moved beyond P and NP -- to things that I'm still struggling to learn. For example, there are complexity classes beyond NP, in the polynomial hierarchy. Also there is the analytical hierarchy which is different from the polynomial one. Very often I see logical problems being described in the analytical hierarchy. For example, abduction and induction are both higher in the analytical hierarchy than SAT. I guess our problem would involve abductive and inductive learning, so it would be strictly harder than SAT. No doubt that we'd employ heuristics, so the worst-case complexity is not a show-stopper. But still, there is the possibility that the problem would be too hard using realistic computing power. YKY ------------------------------------------- agi Archives: http://www.listbox.com/member/archive/303/=now RSS Feed: http://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: http://www.listbox.com/member/?member_id=8660244&id_secret=95818715-a78a9b Powered by Listbox: http://www.listbox.com
