> Then there's the problem of figuring out if you've already enumerated a molecule. That problem has no known polynomial-time solution (graph isomorphism), alth

> Then there's the problem of figuring out if you've already enumerated a molecule. That problem has no known polynomial-time solution (graph isomorphism), although GDB's low node count mitigates the problem. It's not just the low vertex count that makes this an easier problem than general GI. The state of the art GI algorithm for general graphs runs in quasipolynomial time 2^{O((log n)^c)}, with c=3 claimed. [0] However, structural constraints implied by chemical plausibility should (probably[1]) usefully limit the class of graphs that need be considered to those of bounded treewidth. A polynomial time GI algorithm was recently published for graphs of bounded treewidth. [2] [0]: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#State_of_the_art https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Stat... [1]: If nothing else, maximum degree restrictions imposed by chemical valence should impose a useful upper bound on treewidth. Although I (somewhat surprisingly) can't find a paper offhand stating such an explicit bound for treewidth in terms of maximum degree, I did find one stating an asymptotic bound of (1 - C * exp (-4.06√d)|V| for sufficiently large max degree d, and some constant C, which lends some plausibility to this line of thought: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0120880 https://journals.plos.org/plosone/article?id=10.1371/journal... [2]: https://arxiv.org/abs/1803.06858 https://arxiv.org/abs/1803.06858