All very true. Which is one reason I dislike all talk of "complexity" - particularly in such a fuzzy context as debates with creationists.

But we do all have some intuitions as to what we mean by complexity in this context. Someone, I believe it was you, has claimed in this thread that evolution can generate complexity. I assume you meant something other than "Evolution harnesses mutation as a random input and hence as a source of complexity".

William Dembski is an "intelligent design theorist" (if that is not too much of an oxymoron) who has attempted to define a notion of "specified complexity" or "Complex Specified Information" (CSI). He has not, IMHO, succeeded in defining it clearly, but I think he is onto something. He asserts that biology exhibits CSI. I agree. He asserts that evolution under natural selection is incapable of generating CSI - claiming that NS can at best only transfer information from the environment to the genome. I am pretty sure he is wrong about this, but we need a clear and formal definition of CSI to even discuss the question intelligently.

So, I guess I want to turn your question around. Do you have some definition of "complexity" in mind which allows for correct mathematical thinking about these kinds of issues?

I talked to one fellow about GO playing AI last night and I mentioned these Restricted Boltzmann Machines. If the GO problem can be cast as an image processing problem, RBMs might be worth looking into: http://www.youtube.com/watch?v=AyzOUbkUf3M Here is a more recent Google Tech talk by Hinton on RBMs http://www.youtube.com/watch?v=VdIURAu1-aU