From: Philip Goetz (philgoetz@gmail.com)
Date: Fri Dec 22 2006 - 13:08:01 MST
On 12/8/06, Mikko Särelä <msarela@cc.hut.fi> wrote:
> On Tue, 5 Dec 2006, Philip Goetz wrote:
> > Things in a computer science program not relevant to AI:
> > Complexity theory, other than knowing the diff between O(nlogn) and O(n*n)
> > (here I'm using "complexity theory" to refer to i.e. understanding the
> > difference between recursive, recursively enumerable, and
> > co-recursively-enumerable, not to "complexity studies" a la the Santa
> > Fe Institute)
>
> I disagree. By the way, there's two distinct things: algorithmic
> complexity and theory of computational complexity. In my opinion, at least
> basic knowledge of the latter is quite important for AGI.
>
> It is quite useful to understand the difference between class of problems
> that are in P and those that are in NP. The difference between class of
> problems that are in NP and those that are NP hard. The reasons we don't
> know whether P=NP and how that affects our judgements about the
> possibility of efficiently solving certain kinds of problems.
It would be useful to a cryptologist. It might be useful to someone
developing a quantum computer, or a biocomputer. But I don't think
the distinction between NP, NP-complete, and NP-hard has ever been of
the slightest use to me in AI.
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:57 MDT