Entropic cost to accurately solve the boolean satisfiability problem using a stochastic discrete system.

It has long been recognized that information processing is intimately intertwined with the physical system that carries out that processing. This connection implies that information processing is associated with an entropic cost, as famously expressed in Landauer's bound for memory erasure. A more general example of information processing is with the satisfiability problem, whose difficulty can fall into different computational classes such as P or NP. Proposals have been put forwards to gain insights into NP-problems through their expressions as chemical networks. At the same time, computation in such systems is inherently stochastic, meaning the accuracy of the computation is an interesting quantity. I will present a set of results that connect the accuracy to the entropic cost of computation in stochastic processes. Based on explicit examples of stochastic systems aimed at solving the boolean satisfiability problem, we study the thermodynamics of the problem leading to an accuracy-cost trade-off. This trade-off is shown to be system-size dependent.