the only known algorithms that produce optimal solutions are of the 'try-all-possibilities' variety and can have running times that are exponential in the size of the input” - the famous “traveling salesman problem (TSP).You can find out about it on Wikipedia here.
(Aho, Hopcroft and Ullman, “Data Structures and Algorithms”)
The concept is simple. A road network connecting a number of cities is an undirected graph with weights (i.e. lengths) on the edges; a tour is a simple cycle that includes all the vertices, and the aim is to determine the shortest tour.
An exhaustive trawl through every single sequence connecting all vertices in all cases is computationally prohibitive – for example, in the Wikipedia article, an example is given:
In March 2005, the travelling salesman problem of visiting all 33,810 points in a circuit board was solved using CONCORDE: a tour of length 66,048,945 units was found and it was proven that no shorter tour exists, the computation took approximately 15.7 CPU years.However, work has been done on algorithms that come up with results that are known to be close to (within a few percent of) the best answer.
People who are convinced about the ability of evolution to account for the appearance of all life work on the basis that, whilst evolutionary processes may not determine the single best answer, natural selection provides a means for determining one which is close to optimum. It is unfortunate that too much of the objection to evolution as a theory has been founded on the underlying thought that a single optimum solution has to be found for evolution to work. For example, many books talk about the probabilities of an exact 100 amino acid sequence appearing by chance – an argument that unsurprisingly receives short shrift from darwinists.
Proteins, with their enzymatic functions, can be considered “solutions” to the “problems” that an organism faces. For example, a cell has the “problem” of requiring energy. The large scale solution is to use ATP for this. However, this large scale solution has to be broken into many smaller steps – the organism must either find a source of ATP, or have a means of manufacturing it from other molecules. Then for ATP to be useful, other proteins must be able to harness the energy released in chemical processes involving it.
I wanted to give a couple of my own thoughts on whether random mutation and natural selection provide an adequate “problem-solving” mechanism for evolution to take place.
(Micro-evolution) Do mechanisms exist within organisms that permit a “solution” to be optimised in an organism, or for a solution to adapt to a gradually changing environment?
The short answer to this question is yes. A mutation within the gene coding for a protein will result in a change to that protein. The change may be neutral, beneficial or harmful. If beneficial, then the organism that bears the mutation will have a selective advantage, which will be reflected in its descendants.
However, I suspect that it isn't quite as simple as that. For natural selection to work, the number of mutations must be limited in each reproduction. If there are too many mutations, then the beneficial or harmful impact of any particular mutation will be lost. I don't think that Darwinism really has an explanation firstly as to how the DNA and protein mechanisms that allow the reliable duplication of the genetic material in an organism came about, and secondly how they could have a mutation rate that is neatly adapted to natural selection at all. Or rather, I suspect the answer is that “this was the evolutionary favoured rate” - which, without any real empirical foundation, would be a “evolution did it” sort of answer.
(Macro-evolution) Do mechanisms exist within organisms that allow for the appearance of functionality when it wasn't present before?
The short answer to this question, in my opinion, is no. There are exceptions – for example, the appearance of antifreeze glycoproteins in notothenioid fish, and the appearance of the ability to digest nylon in some bacteria. These are both significant evolutionary steps. But details of the changes have been analyzed in both cases, and the amount of new information added in either case was not significant. Also, in both cases, there is little investment on the part of the organism in any individual offspring – a situation not really typical of land-dwelling chordates in which we see today such a great variety of morphologies.
Macroevolution can't continually point to co-option of existing proteins into new roles. At some stage, new proteins have to be generated. This requires random – or randomised, or frameshifted – sequences, the generation of random polypeptides and their acceptance by the organism when the organism has no means of knowing whether they are going to be of any use, the presence or later addition of controlling mechanisms around the gene and so on. For the earliest organisms, the significant numbers of genes required (see the post below) have to be generated and organised – and many of these genes being shared as I understand by all life, they are likely to have been present in the earliest of our putative common ancestors. We don't even have a handle on the scale of the problems presented by macroevolution at this stage. The assertion that evolution did it has no empirical foundation – it is an assertion founded on the priority of the paradigm, rather than on scientific fact.
I will be challenged that I have no alternative mechanism, and that, in accordance with the scientific method, darwinists will at least continue to look for mechanisms whilst they can. I don't have a problem with that – and indeed, I have used and will in future probably use my time to see what can be done to model evolutionary processes. It is worth pointing out that few proponents of ID have a problem with that either. But based on my understanding of the problems involved, I am simply not convinced that darwinism will be able to offer a meaningful solution.