Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!mit-eddie!ll-xn!ames!ucbcad!ucbvax!WISDOM.BITNET!eitan
From: eitan@WISDOM.BITNET (Eitan Shterenbaum)
Newsgroups: comp.ai.digest
Subject: Re: Success of AI
Message-ID: <4357@wisdom.BITNET>
Date: Thu, 5-Nov-87 09:31:12 EST
Article-I.D.: wisdom.4357
Posted: Thu Nov  5 09:31:12 1987
Date-Received: Wed, 11-Nov-87 04:42:48 EST
References: <8710280748.AA21340@jade.berkeley.edu>
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: eitan%H@wiscvm.arpa (Eitan Shterenbaum)
Organization: The Weizmann Institute of Science, Rehovot Israel
Lines: 38
Approved: ailist@kl.sri.com



In article <> honavar@speedy.wisc.edu (A Buggy AI Program) writes:
>
>Discovering that a problem is NP-complete is usually just the
>beginning of the work on the problem. The knowledge that a problem is
>NP-complete provides valuable information on the lines of attack that
>have the greatest potential for success. We can concentrate on algorithms
>that are not guaranteed to run in polynomial time but do so most
>of the time or those that give approximate solutions in polynomial time.
>After all, the human brain does come up with approximate (reasonably good)
>solutions to a lot of the perceptual tasks although the solution may not
>always be the best possible. Knowing that a problem is NP-complete only
>tells us that the chances of finding a polynomial time solution are minimal
>(unless P=NP).
>

You are right and so am I,
        a) There're no polynomial algorithms, which are known to us, that can
            solve NP problems.
        b) There are approximate and probabilistic *partial* solutions for NP
           problems.
As to the claim "the brain does it so why shouldn't the computer" -
It seem to me that you forget that the brain is built slightly differently
than a Von-Neuman machine ... It's a distributed enviorment lacking boolean
algebra. I can hardly believe that even with all the partial solutions for
all the complicated sets of NP problems that emulating a brain brings up, one
might be able to present a working program. If you'd able to emulate mouse's
brain you'd become a legend in your lifetime !
Anyway, no one can emulate a system which has no specifications.
if the neuro-biologists would present them then you'd have something to start
with.

And last - Computers aren't meta-capable machines they have constraints,
           not every problem has an answer and not every answermakes sense,
           NP problems are the best example.

                        Eitan Shterenbaum