  The promise of chemical computation lies in controlling systems incompatible
with traditional electronic micro-controllers, with applications in synthetic
biology and nano-scale manufacturing. Computation is typically embedded in
kinetics---the specific time evolution of a chemical system. However, if the
desired output is not thermodynamically stable, basic physical chemistry
dictates that thermodynamic forces will drive the system toward error
throughout the computation. The thermodynamic binding network (TBN) model was
introduced to formally study how the thermodynamic equilibrium can be made
consistent with the desired computation, and it idealizes tradeoffs between
configurational entropy and binding. Here we prove the computational hardness
of natural questions about TBNs and develop a practical algorithm for verifying
the correctness of constructions by translating the problem into propositional
logic and solving the resulting formula. The TBN model together with automated
verification tools will help inform strategies for error reduction in molecular
computing, including the extensively studied models of strand displacement
cascades and algorithmic tile assembly.
