Supplementary Files for "Chemical Reaction Networks and Stochastic Local Search"

The example CRNs discussed in the paper can be run by downloading this tarball containing Mathematica notebooks and associated files.

To run the CRN simulations, we use the slightly outdated 2016 version of David Soloveichik's CRN simulator, with modifications by Erik Winfree that make it more efficient for large CRNs. Everything needed -- except Mathematica itself -- is included in the tarball above. The code was tested on Mathematica 10, 11, and 12, on MacOS El Capitan to Mojave. It is essential that the Mathematica Compile[] function is properly configured, which it should be by default unless your machine doesn't have a compiler installed. Without a compiler, everything will be insanely slow.

The notebooks are designed to be tried out interactively by a user who tests stuff out as they go along, bit by bit. Often example commands are given in lieu of an explanation. Don't just try everything though: some examples will take a very long time to run. So think about it first.

Covering material in the same order as the paper:

"CircuitsAndFunctions.nb" illustrates how to build CRNs to evaluate Boolean circuits, to solve circuit satisfiability problems, and to solve formula satisfiability problems. Three constructions are provided for the latter: the simplest, most naive CRN, FormulaSATCRN; the WalkSAT-inspired CRN highlighted in the paper, WalkSATCRN; and the provably-correct CRN hinted at in Footnote 2, StumbleSATCRN. The notebook also details how the timing comparisons of Figure 3 were done.

"RecognizingAndGeneratingPatterns.nb" provides details for the examples in Figure 4. The method for building an associative-memory Boolean formula based on Cook's network-of-relations approach is explained and demonstrated. The construction for membrane-maintaining constraints is provided. Both are illutrated with movies that are fun to watch.

"Sudoku.nb" explains the randomized depth-first-search CRN in much more detail than was provided in the paper. If you have Sudoku problems that you can't solve, just run our CRN simulator!