From: Mikko Särelä (msarela@cc.hut.fi)
Date: Thu Dec 07 2006 - 22:00:19 MST
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.
Theory of computational complexity has almost nothing to do with whether
an algorithm has a complexity of O(n) or O(nlogn). That's the area for
algorithmic complexity. It may tell you that you cannot make an algorithm
that is faster than certain complexity - with certain assumptions. It can
also tell you whether one can create an efficient approximative solver, or
efficient distributed algorithms for a certain class of problems.
It can also tell you, and give you an intuition, of what happens when you
change a problems - just a little bit. Sometimes small changes can have
huge effects on computational complexity of problems - and you wouldn't
want to work with an architecture that e.g. made verifying wanted
properties of self-modification cryptographically hard. [You might be
willing to accept NP hardness, though, if the category of problems was
such that you could limit yourself to those instances of the problem space
that _are_ easy to solve].
--
Mikko Särelä http://thoughtsfromid.blogspot.com/
"Happiness is not a destination, but a way of travelling." Aristotle
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:57 MDT