[Houshalter]

Practically speaking, intelligence is just the ability to achieve your goals. An AI, ideally, would have some kind of utility function and make predictions about what actions will lead to the highest utility. The better the AI, the better it's ability to make predictions and get the outcomes it wants.

The amount of complexity is irrelevant. There are terribly complicated algorithms which do worse than simple ones.

[tekromancr]

I think part of it would be formulating goals. If you have a process that can very rapidly sum numbers, it ranks lower than one that is incapable of that speed, but can decide that summing numbers is a means to accomplish that goal.