High‐Concentration Chemical Computing Techniques for Solving Hard‐To‐Solve Problems, and their Relation to Numerical Optimization, Neural Computing, Reasoning under Uncertainty, and Freedom of Choice

Chemical computing – using chemical reactions to perform computations – is a promising way to solve computationally intensive problems. Chemical computing is promising because it has the potential of using up to 10 molecules as processors working in parallel – and thus, has a potential of an enormous speedup. Unfortunately, for hard-to-solve (NPcomplete) problems a natural chemical computing approach for solving them is exponentially slow. In this chapter, we show that the corresponding computations can become significantly faster if we use veryhigh-concentration chemical reactions, concentrations at which the usual equations of chemical kinetics no longer apply. We also show that the resulting method is related to numerical optimization, neural computing, reasoning under uncertainty, and freedom of choice. 1 What Are Hard-so-Solve Problems and Why Solving Even One of Them Is Important What is so good about being able to solve hard-to-solve problems from some exotic class? In this paper, we will talk about applying chemical computing to a specific class of hard-to-solve (NP-complete) problems. To a person who is not very familiar with the notions of NP-completeness, this may sound like a very exotic (and thus not very interesting) topic. For example, this person may ask: OK, we spend all these efforts and solve prob-