Registered: Oct 2003
Posts: 38

There is an unresolved tension in NKS regarding the complexity of optimal solutions to problems.

On the one hand, there are linear conguential generators that achieve a maximal period through essentially simple means. (p321)

And on the other hand, there is the idea that the fastest algorithms for a particular task will likely have a seemingly random structure.(p1141)

There are a few other cases of optimization that don't fall directly on this continuum - natural selection, and the search for meaning in programs (the input-doubling rules of p833).

One can argue that in the linear conguential generator case, one is trying to satisfy a simple constraint. And as we see in chapter 7, most constraints that can be at all satisfied are satisfied in simple ways.

And one can argue that if you try to minimize a quality that is 'internal' to the algorithm, as runtime is, one will likely get something complex.

While this seems intuitively correct, I would really like something more concrete to sink my teeth into. One gets the feeling that answering a question like this leads to some deep insight...

Any ideas?

__________________
Everything is an expression.

Report this post to a moderator | IP: Logged