# How hard is the origin of life problem?

The origin of life problem is the wide-ranging inquiry into the mechanisms underpinning the emergence of life, where one definition of life is "a self-sustained chemical system capable of undergoing Darwinian evolution" [1].

In one model - the "RNA world" hypothesis [2] - a sea of self-replicating RNA molecules are the precursors to cellular organisms. The mechanism behind the emergence of RNA from the prebiotic chemicals found on earth's surface is an open problem. However, in a series of groundbreaking results, the Sutherland Group at the University of Manchester described a plausible mechanism that combines prebiotic feedstock molecules to yield 2 of the 4 nucleotide types (ribocytidine, ribouridine) found in RNA [3].

From a computational complexity perspective, what can be said in general about the difficulty of reverse-engineering the remaining nucleotides found in RNA? That is, the problem of determining if a desired organic molecule is "reachable" using basic chemical reactions from the set of less-complex molecules thought to be abundant on the earth's surface. Are there any phase transition conditions which would make it easier or harder to reverse engineer a molecule, similar to the phase transitions found in satisfiability problems [4]?

The problem is related to retrosynthetic analysis (for which Elias James Corey received the Nobel Prize in chemistry in 1990) and computer-assisted organic synthesis, however when considering the origins of life, we tend to think of a primitive environment where the available building blocks and plausible pathways leading to good yields are constrained compared to a modern wetlab.

Another approach is the metabolism first model, where cyclical chemical reactions based on small molecules evolve to develop increasingly complex structures.

The generalized, abstract problem of determining reachable outcomes given a set of starting materials and allowable reactions is undecidable when the number of steps is unconstrained and NP-hard when bounded [5]. This observation however does not say how difficult the organic chemistry we actually see in our world is.

In general, basic organic chemistry is not Turing-complete because termination is decidable [6]. However, stochastic chemistry [7] can approximate Turing machines to arbitrary precision [8]. Arbitrary protein structure prediction (protein folding) is known to be NP-complete [9].

There are some machine learning methods for assessing whether or not a particular target compound or drug is likely to be synthesizable [10]. Does this approach say anything about RNA/DNA?

The problem of RNA formation may be completely tractable even if the more general problem of organic synthesis is intractable. This would mirror the situation in physics. Deducing the dynamical equations governing an arbitrary physical system is NP-hard [11], however the physics we encounter in our world is much easier to analyze and appears to be tractable (what has also been called "the unreasonable effectiveness of mathematics in the natural sciences" [12]).

[1] http://originlife.org/
[2] http://en.wikipedia.org/wiki/RNA_world_hypothesis
[3] http://www.nature.com/nature/journal/v459/n7244/full/nature08013.html
[4] http://www.cs.ubc.ca/~kevinlb/papers/2012-PredictingSatisfiability.pdf
[6] http://dna.caltech.edu/Papers/sCRN_computation_2008.pdf
[7] http://demonstrations.wolfram.com/DeterministicVersusStochasticChemicalKinetics/
[8] http://lucacardelli.name/Talks/2009-05-08%20Biochemistry%20%28Warsaw%29.pdf
[9] http://www.bentribelhorn.com/files/cs524.pdf
[10] http://www.dtc.umn.edu/publications/reports/2010_02.pdf
[11] http://arxiv.org/pdf/1005.0005.pdf

• So you want to say that we have a set of Chemical Materials(Molecules) and Chemical Operations as their operations. We want to derive a specific Molecule like RNA or DNA using these operations from some base or random molecules ?! – Kamran Amini Jun 9 '12 at 23:45
• it seems fair to say, as a rough lower bound, this problem is easily at least as hard as the protein folding problem which has been proven NP complete in somewhat-toy models. and conservatively, the complexity is much harder. – vzn Jun 11 '12 at 15:16
• the question also seems vague or poorly defined. "That is, the problem of determining if a desired organic molecule is "reachable" using basic chemical reactions from the set of less-complex molecules thought to be abundant on the earth's surface." but RNA/DNA definitely already fit that definition. they are built out of less complex molecules (than the proteins) that are abundant on earth's surface. actually that definition holds for all biologically-constructed proteins also. therefore, suggest the question be edited/clarified. – vzn Jun 11 '12 at 15:20
• I'm uncomfortable with the mix of "computational complexity" (which is a purely mathematical formalization of limiting behavior as problem sizes grow to infinity) and the insistence on "chemistry we actually see in our world". Without a formal mathematical model of "real world chemistry", which allows for unboundedly complex molecules, the problem isn't well defined. In particular, the assertion that "basic organic chemistry is decidable" is obviously wrong without very strong assumptions about "basic organic chemistry", like "the number of atoms in the universe is finite". – Jeffε Jun 11 '12 at 15:21
• the actual "origin of life" problem in chemistry/biology as I understand it is more how life could arise incrementally/near spontaneously from chemicals at the earths surface through random recombination/mixing and later, after a small basic complexity in structure is achieved that permits some rudimentary form of "inheritance", principles of evolution, not nec restricted to DNA type inheritance/evolution, but later that arising also.... ie in a sense how the highly ordered/animated structure of life could arise from unanimated materials through billions of years of chance mixing.... – vzn Jun 12 '12 at 15:47