A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > Complexity and simplicity in optimal solutions
  Last Thread   Next Thread
Thread Post New Thread    Post A Reply
Kovas Boguta
Wolfram Science Group

Registered: Oct 2003
Posts: 38

Complexity and simplicity in optimal solutions

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

Old Post 01-23-2004 08:53 AM
Kovas Boguta is offline Click Here to See the Profile for Kovas Boguta Click here to Send Kovas Boguta a Private Message Visit Kovas Boguta's homepage! Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-16 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives