Infinite Dilemma 1: Not Enough Time
Neo-Darwinistic Concept of Time Through the Lens of Computational Complexity
If evolution is a computing problem, how has nature solved it? Furthermore, how is it related to AI, the culmination of computing? According to Neo-Darwinism, or the modern synthesis of Charles Darwin’s evolutionary theory of the origin of life, nature has taken blind chances over a long enough time in selecting variations among genetic mutations. In this article, I attempt to study the Neo-Darwinistic concept of time through the lens of Computational Complexity.
Blind Watchmaker
The Neo-Darwinists’ “central dogma” says :
When given enough time through a verification process, such as natural selection, Chances can lead to diversity, creativity, and ingenuity no matter how rare they are.
“One has only to wait; time itself performs miracles (Wald, 1954, 48–53),” argued physiologist and Nobel laureate George Wald. Sometimes, rareness is challenged, such as in the watchmaker analogy, in which critics say that if you find a watch on the ground, we can infer that someone must have dropped it and that there must have been a watchmaker who made it. However, Richard Dawkins claims that even though nature is like the improbable blind watchmaker, time turns improbability into reality. “The living results of natural selection overwhelmingly impress us … with the illusion of design and planning (Dawkins, 1985).” In other words, a watch can be an accidental product of a blind watchmaker who has neither awareness of what a watch is nor any plan to make one.
While the debate about the blind watchmaker is metaphorical and can never be settled, such an overarching claim of explanatory power, if incontrovertibly refuted in a different case, will be the Achilles heel of Neo-Darwinism.
Random Guesser and Math Genius
Here is that such a thought experiment:
Given enough time, can a random guesser, who is well versed in following logical rules, but has no mathematical intuition, solve problems like a math genius?
If you ask Neo-Darwinists, they will have to insist that the random guesser demonstrates the creativity and ingenuity of a math genius due to their central dogma. However, mathematicians would say, “No, it’s mathematically impossible.” Computer scientists would respond that it’s computationally infeasible. Unlike the blind watchmaker, the random math guesser experiment can find its counterpart in mathematics and computer science so that we can settle the debate decisively.
Let’s start at the dawn of the twentieth century, when math formalists, led by prominent mathematician David Hilbert, made logical reasoning an integral part of math. In doing so, they could treat problem-solving as part of math. They considered intuition thought artifacts and therefore unnecessary for mathematical development. As a result, Hilbert proposed Hilbert’s program, which could unfold mathematics completely from a set of axioms and logical rules.
Knowing that Hilbert’s program ultimately failed, what necessary role can we conclude that intuition plays? Intuition “guesses’’ the right axioms to start with, the salient math facts to study, and the necessary logical steps to prove those facts. Then logic is used for verifying those guesses. As we can see, in Hilbert’s time, mathematicians downplayed the art of guessing and believed it could be “purified” away with random guessing. Thus, our random-guesser thought experiment is equivalent to Hilbert’s program. If it worked, mathematical development could be blind, purposeless, and unplanned, exactly how Neo-Darwinists describe the evolution of life.
Let’s now move on to Kurt Godel and Alan Turing, who proved that Hilbert’s program was mathematically impossible due to the inevitable paradoxes from self-references. Not only is intuition necessary to continuously refine and extend axioms, according to Godel, but it also must be involved in discovering and proving math facts, according to Turing (see my article, The Limit of Logic and the Rise of the Computer).
Mathematical development needs intuition, implying that nature might not be blind after all.
Math and Computer Science
Two weaknesses in math explain the mathematical falsehood in Hilbert’s program. First, it lacks the concept of the time required to solve a problem. Second, it does not have a guessing tool. Paradoxically, such shortcomings in mathematics resulted in the computer and computer science.
Computer science defines the time in processing steps to run a program and is equipped with a tool called “searching” to handle guessing. Random and artful guesses correspond to brute-force and smart searches, respectively. The minute probability of correct guessing can be associated with searching in a large space through brute force and over a long-running time.
To summarize:
- The running time of a brute-force search is proportional to search space size.
- The probability of making the right guess is proportional to one over the size of the search space.
Now, we can treat a mathematical problem on solving problems as a computational one and study mathematical possibility as computational feasibility. Regarding feasibility, we can classify computing problems into the following 2 types according to whether their running times or search spaces grow exponentially or polynomially. We can consider the first type as infeasible since an exponential running time or search space can outgrow even the cosmos. The second type, referred to as P standing for Polynomial-time, is considered feasible since a polynomial running time or search space generally can be accommodated within the limits of the cosmos.
P vs. NP: Ask a Neo-Darwinist
It is hopeless to deal with infeasible problems, and feasible problems seem too easy to be of significance. Fortunately, there is a third type, referred to as NP, standing for Non-deterministic Polynomial-time. Making the right guess is potentially difficult (exponential time), but verifying a guess is easy (polynomial time). We consider Hilbert’s program an NP problem since it is feasible to verify guesses using logical reasoning but infeasible if guessing randomly or searching by brute force.
Likewise, a blind, purposeless, and unplanned evolution according to Neo-Darwinism is like solving an NP problem with a brute-force search. Natural selection as the verification mechanism must take polynomial time; otherwise, it would not facilitate the evolution of life.
As explained in my article, Intuition, Complexity and the Last Paradox, there is a class of NP problems, referred to as NP-complete, considered the most difficult among all NP problems. If there is a polynomial-time solution for an NP-complete problem, all NP problems could be reduced to such a problem and solved in polynomial time, thus proving P = NP. We refer to determining if P = NP as the P vs. NP problem. It is one of the most important open problems in math and computing, or even in modern sciences.
How will a Neo-Darwinist answer the question of whether P = NP? If yes, evolution can be reduced to some NP-complete problem and solved by a polynomial-time NP-complete solver that does not understand life. Thus, nature could still be blind, with creativity, ingenuity, and foresight of evolution still an illusion, as would a Neo-Darwinist expect. However, the nightmare of explaining who designed such a polynomial-time solver would haunt her. As we can see, a Neo-Darwinist will insist on P not being equal to NP.
Emile Borel: Rare Events Do Not Happen
Recall that brute-force searching corresponds to random guessing. As a result, an exponentially growing search space indicates exponential running time and the diminishing probability of guessing correctly. For convenience, we can represent the search space size as 10^N, where N is the number of zeros after 1.
Thus, we can use N to indicate how large the search space is, how long it takes to run the search, and equivalently, how improbable it is to make a right guess. Neo-Darwinists insist no matter how large N is, there is plenty of time to make as many guesses as possible. This position is perhaps best demonstrated in the following quote by George Wald:
Given so much time, the [nearly] “impossible” becomes possible, the “possible” becomes probable, and the “probable” becomes virtually “certain” (Wald, 1954, 48–53).
Contrary to the Neo-Darwinist position about chance and time, Emile Borel, 1871–1956, a prominent French mathematician, said in his “single law of chance (Borel, 1962)”:
Events with a sufficiently small probability never occur; or at least we must act, in all circumstances, as if they were impossible.
Even though it is called the “single” law, it describes two significant scenarios in which we consider sufficiently small probabilities zero — the former concerns how you make everyday or lifetime decisions. For example, you want to drive to work, risking being killed in a car accident, carry an umbrella every day given that the weather forecast is not always correct, or bet your retirement on winning a lottery.
The second scenario concerns how you deal with scientific facts or engineering decisions. Borel estimated a probability smaller than N = 50, the number of zeros following 1 in the dominator, that Newton’s Laws might be violated. But we would consider such a probability as zero when designing a bridge, a car, an airplane, and landing men on the moon. Moving further, considering predictions by statistical mechanics, we need not consider the possibility that a mixture of oxygen and nitrogen in a container spontaneously separates into pure nitrogen on the right half and pure oxygen on the left. The size of the search space of each atom deciding to go right or left is N in the hundreds of millions, so much larger than our cosmos in every aspect that Borel considered such a search space size to be on the super-cosmic scale.
For the evolution of life, renowned evolutionary biologist, Carl Sagan, estimated a search space of N = 2,000,000,000, or a chance of 1 over 10 raised to the power of 2 billion, to match Neo-Darwinistic theory that life could evolve on any single given planet entirely by chance (Sagan, 1973). However, Neo-Darwinists argue that their evolution mechanism is not entirely random and natural selection is the non-random element (Dawkins, 2006). As mentioned before, if evolution is considered an NP problem, natural selection is the verification mechanism. According to microbiologist James Shapiro, “Without variation and novelty, selection has nothing to act upon” (Shapiro, 2011). The only way to make it feasible or probable is to have non-randomness in the guessing or searching, meaning there is design or planning in generating the variations, strictly forbidden in the central dogma.
Beyond P vs. NP
We have successfully employed heuristic and approximate solvers, despite having the worst-case exponential time, in mathematics, chip design, software checking, and mission-critical decision-making in various areas concerning our everyday lives. At the same time, we are witnessing AI making headway in solving NP-complete problems in mathematics by imitating math geniuses (Bansal et al., 2019)(Polu & Sutskever, 2020) (Selsam et al., 2019).
In biology, Levinthal’s paradox has been confronting Protein Structure Prediction (PSP) to determine the 3-dimensional structure from a protein’s linear sequence of amino acids. The paradox says
Despite its enormous search space, with N approximately 300, even for a small protein molecule, it folds spontaneously on a millisecond or even microsecond time scale.
Scientists thought the PSP was NP-complete (Unger & Moult, 1993) (Unger & Moult, 1993). Recently, DeepMind claimed a breakthrough in using AlphaFold, an AI program, to solve the PSP with unprecedented accuracy and efficiency. Now a question is as follows: doesn’t AlphaFold’s success prove P = NP if it indeed “solves” the PSP, a known NP-complete problem? The answer is no since AlphaFold is academically categorized as one of the approximate and heuristic solvers. However, AlphaFold and AI solutions stand out in the following aspects compared to others:
- Even in the worst case, they do not have an exponential running time
- They are always “open” and continuously learning and adapting
- As explained below, they can be designed to be end-to-end to capture the intuition of humans or nature
The previous claims of the PSP being NP-complete might be due to a mismatch between nature and handcrafted problem formulations, which causes exponential inflation of the search space (Bahi et al., 2013). Instead, AlphaFold learns from nature to map an amino sequence of a protein directly to its final 3-dimensional structure in an end-to-end fashion. Rather than jumping around in a super-cosmic search space, it sees the search space as a landscape and navigates its way to find the bottom.
In this sense, AI provides practical solutions to challenging problems and enlightens us about how nature and humans might similarly solve problems. A more profound question is how nature selects those sequences of amino acids which can fold into 3-dimensional structures. An intriguing observation is that “the energy landscape used by nature over evolutionary timescales to select protein sequences is essentially the same as the one that folds these sequences into functioning protein (Morcos et al., 2014).” Nature might have evolved by navigating through an evolutionary landscape.
What If Rare Events Happen?
Neo-Darwinists argue that nature is not solving any problems. It is more like a simulation than blindly moves forwards with no goals; any achievements are purely accidental.
A review of Carroll’s 2020 book noted, “A Series of Fortunate Events tells the story of the awesome power of chance and how it is the surprising source of all the beauty and diversity in the living world.“ The similarly titled book “A Series of Unfortunate Events” (Snicket, 1999–2006) might have inspired the choice of the book title. In the earlier book, the children of the Baudelaire family suffer from a series of tragic accidents, starting with losing their parents in a fire. In contrast to Carroll’s adoration of chance, the Baudelaire children might blame chance as the source of suffering and destruction.
Chance is neither good, as seen by Carrell and his fellow Neo-Darwinists, nor bad as might be felt by the Baudelaire children. It is a measure of uncertainty of something that has not happened yet. Once something happens, it is called an event. How do we react when a supposedly rare event happens? Following plausible reasoning (Polya, 1954), the Baudelaire children figure that when a series of nearly impossible events do happen, it is almost certain that there is an evil mastermind, who turns out to be Count Olaf, conspiring against them.
On the other hand, trying to link cosmic events to one’s existence sounds like a job for moral leaders or spiritual teachers, whose roles Neo-Darwinists somehow aspire to play. It is a categorical mistake to explain away the detail by resorting to chance and time.
A Scientific Mind
Since the inception of Neo-Darwinism, there have been flourishing research studies (The Third Way of Evolution) (Koonin, 2012) (Shapiro, 2011) (Jablonka & Lamb, 2005) (Carey, 2012) (Woodward & Gills, 2012)(Noble, 2017) suggesting that Neo-Darwinism is insufficient to explain evolution. It desperately needs amendments with new scientific findings.
For example, a theory that’s drastically different from Neo-Darwinism is symbiogenesis, of which biologist Lynn Margulis is one of the major discoverers. She had the following dialogue with Dawkins (Noble, 2017):
Dawkins: It [Neo-Darwinism] is highly plausible, it’s economical, it’s parsimonious, why on earth would you want to drag in symbiogenesis when it’s such an unparsimonious, uneconomical [theory]?
Margulis: Because it’s there.
The jury is still out on whether nature has exactly evolved as Neo-Darwinism describes. I maintain that a scientific mind does not stop at a theory because it is parsimonious and elegant. Instead, its insatiable curiosity and discipline of plausible reasoning compel it to pursue the devil in detail.
Bibliography
Aaronson, S. (2016). P=?NP. In Open Problems in Mathematics. Springer.
Bahi, J. M., Bienia, W., Cote, N., & Guyeux, C. (2013). Is Protein Folding Problem Really an NP-complete One? First Investigations. Journal of Bioinformatics and Computational Biology, 12(1).
Bansal, K., Loos, S., Rabe, M., Szegedy, C., & Wilcox, S. (2019). HOList: An Environment for Machine Learning of Higher-Order Theorem Proving. Proceedings of the 36th Conference on Machine Learning.
Borel, E. (1962). Probabilities and Life (M. Baudin, Trans.). Dover Publishing.
Borel, E. (1963). Probability and Certainty. Walker and Co.
Carey, N. (2012). The Epigenetic Revolution: How Modern Biology Is Rewriting Our Understanding of Genetics, Disease, and Inheritance. Columbia University Press.
Carroll, S. B. (2020). A Series of Fortunate Events: Chances and the Making of the Planet, Life and You. Princeton University Press.
Dawkins, R. (1985). The Blind Watchmaker. Norton & Company, Inc.
Dawkins, R. (2006). The God Delusion. Houghton Mifflin Co.
Dawkins, R. (2010). The Greatest Show on Earth: The Evidence of Evolution. Free Press.
Hart, W., & Instrail, S. (1977). Robust proofs of NP-hardness of Protein Folding: General Lattices and Energy Potentials. Journal of Computational Biology, 4(1), 1–22.
Jablonka, E., & Lamb, M. J. (2005). Evolution in Four Dimensions: Genetic, Epigenetic, Behavioral, and Symbolic Variation in the History of Life. The MIT Press.
Jaynes, E. T. (2003). Probability Theory: The Logic of Science (10th ed.). Cambridge University Press.
Koonin, E. V. (2012). The Logic of Chance: The Nature and Origin of Biological Evolution. Pearson Education, Inc.
Morcos, F., Schafer, N. P., Cheng, R. R., Onuchic, J. N., & Wolynes, P. G. (2014, August 26). Coevolutionary Information, Protein Folding Landscapes, and The Thermodynamics of Natural Selection. Proceedings of National Academy of Sciences of The United States of America.
Noble, D. (2017). Dance to the Tune of Life: Biological Relativity. Cambridge University Press.
Polu, S., & Sutskever, I. (2020, September 7). Generative Language Modeling for Automated Theorem Proving. https://arxiv.org/abs/2009.03393.
Polya, G. (1954). Mathematics and Plausible Reasoning. Princeton University Press.
Polya, G. (1954). Mathematics and Plausible Reasoning. Princeton University Press.
Selsam, D., Lamm, M., Bunz, B., Liang, P., Dill, D. L., & de Moura, L. (2019, March 12). Learning a SAT Solver from Single-Bit Supervision. https://arxiv.org/abs/1802.03685.
Shapiro, J. A. (2011). Evolution: A View from 21st Century. James A. Shapiro.
Snicket, L. (1999–2006). A Series of Unfortunate Event. HarperCollins Publishers LLC.
Unger, R., & Moult, J. (1993). Finding the lowest free energy conformation of a protein is an NP-hard problem: Proof and implications. Bulletin of Mathematical Biology, 55(6), 1183–1198.
Wald, G. (1954, August). The Origin of Life. Scientific American, (191), 45–53.
Woodward, T. E., & Gills, J. P. (2012). The Mysterious Epigenome: What Lies Beyond DNA. Kregel Publications.
