On 11/24/06, Richard Loosemore <[EMAIL PROTECTED]> wrote:
I have seen this kind of computational complexity talk so often, and it is just (if you'll forgive an expression of frustration here) just driving me nuts. It is ludicrous: these concepts are being bandied about as if they make the argument wonderfully rigorous and high-quality .... but they mean nothing without some explicit specification of assumptions.
I have a similar feeling. In many cases, the notion of "computational complexity" has been misused when applied to thinking processes. By definition, this notion is about an algorithm applied to a problem class, and maps the size of a problem instance to the time the algorithm spends in the solution. When talking about a human problem-solving process, such as "designing a NLP mechanism for an AGI", the notion cannot be used in its exact sense, because: (1) We are not trying to solve a "problem class", but a "problem instance". Even if someone successfully designed a NLP interface for an AGI, it doesn't mean that he/she has an algorithm that can design such interfaces for all kinds of AGIs. When problems are solved in a case-by-case manner using various ad hoc methods, these solutions cannot be analyzed as following the same algorithm, with a fixed complexity function. (2) Human thinking processes usually do not follow problem-specific algorithms. As I argued before, I don't have an algorithm for playing chess. You cannot say I have one though don't know it myself, since in different time I move differently at the same position. If you say that my algorithm is "time-dependent" or "context-sensitive", then it is effectively the same as saying I have no chess-specific algorithm. Anyway, the time spent in the solution is not a fixed function of the "problem instance" alone. Furthermore, thinking processes are usually open-ended. If I add a NLP interface for NARS in the future, it will surely be an incrementally improving process, so it will be hard, if possible, to say how much time it takes, since it is probably never finally finished. In summary, like many other math notions, to use "computational complexity" outside math and computer science doesn't always make sense. Of course, the notion can be used metaphorically, or on a "formalization" of the original problem (which turns the problem into a computation), but such a usage has little "rigorous and high-quality" nature with respect to the real problem. The above conclusion doesn't mean that these problems cannot be solved in AI, but that the traditional theory of computation is largely irrelevant in designing and analyzing their solutions. For detailed arguments and explanations, read http://nars.wang.googlepages.com/wang.computation.pdf and http://www.springer.com/west/home/computer/artificial?SGWID=4-147-22-173659733-0 Pei ----- 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
