On 7/15/06, Russell Wallace <[EMAIL PROTECTED]> wrote:
On 7/16/06, Ricardo Barreira <[EMAIL PROTECTED]> wrote:
> Put simply - intelligent beings like us can solve np-hard problems, so
> how could intelligence NOT be NP-hard??
>
Of course anything to do with intelligence is _at least_ NP-hard - anything
so trivial it doesn't even get that far isn't filed under the heading of AI
at all.
But NP-hard is still very, very trivial; there's very little that falls
into that category. Basically there are four important categories of
problem:
1) NP-hard
2) EXPTIME-hard
3) Incomputable
4) Ill-posed problem
Intelligence is primarily in category 4 (which is Richard's point, if I
understand him correctly).
I basically agree, though I'd rather say that what "problem" (as well
as "solution") means in mathematics (and other formal theories) is
different from what it means outside mathematics (such as in everyday
life). Notions like "computability" and "computational complexity"
(therefore, "NP-hard" and so on) are defined on the former type of
"problem", while AI is mostly about the latter. Therefore, "NP-Hard"
is not an applicable concept to most problems that an AI system faces.
A longer argument can be found in
http://www.cogsci.indiana.edu/farg/peiwang/PUBLICATION/wang.computation.pdf
Abstract
The concept of computation, as well as the related concepts algorithm,
Turing machine, computability, and computational complexity,
correspond to a specific mode of using computers to solve problems.
This computational mode assumes the sufficiency of knowledge and
resources with respect to the problem to be solved. From the view
point of Artificial Intelligence, an intelligent mode of problem solving
is introduced, where the problem solving process cannot been seen
as computation anymore. A system working in this mode is briefly
described. Finally, these two modes of problem solving are compared.
Pei
-------
To unsubscribe, change your address, or temporarily deactivate your subscription,
please go to http://v2.listbox.com/member/[EMAIL PROTECTED]
