# 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