Chemistry

Computational Complexity of Synthetic Chemistry Basic Facts

Authors: Warren D. Smith
Comments: 8 Pages. On internet since 1997; uploading to VIXRA for archival purposes. Related paper: Molecular tinkertoys.

Three negative results:

1. Given a set of allowed starting materials and allowed chemical reactions, the problem of determining whether a chemical of specified structure is synthesizable is Turing undecidable.
2. The question of whether it is synthesizable in N steps is NP-complete. These 2 results apply in a general abstract setting and do not prove anything about how hard the problem is with any specific set of starting materials and allowed reactions. In particular we prove nothing about the case when the starting materials are all commercially available chemicals and the reactions are all known reactions!
3. The IUPAC naming scheme for assigning names to organic compounds will assign ambiguous names to most N-atom compounds and requires great chemical expertise. We show that both these problems are avoidable with alternative naming schemes, There are unquestionably {it far} simpler and better methods to name chemical compounds than the IUPAC scheme.

All 3 of these facts are almost trivial from the viewpoint of modern computer science, but I don't think they've been mentioned in the chemical literature.

Positive results: We discuss algorithms for finding out how to solve the synthesis problem (of determining whether something is synthesizable, and what the best synthetic process is). An interesting generalization of the famous "shortest path problem" in directed graphs arises in which the paths become synthetic trees, the graphs become hypergraphs, and the distances become synthetic costs. This problem is soluble either by generalizing Dijkstra's algorithm or the dynamic programming algorithm. Despite the fact that these algorithms are highly efficient as a function of the size of the hypergraph, in practice because the hypergraph arising from chemistry is enormous, that is inadequate. We discuss methods for ameliorating this.
Category: Chemistry