Joshua J. Arulanandham, Cristian S. Calude, Michael J. Dinneen
Solving SAT with Bilateral Computing

Abstract.
We solve a simple instance of the SAT problem using a natural physical computing system based on fluid mechanics. The natural system functions in a way that avoids the combinatorial explosion which generally arises from the exponential number of assignments to be examined. Besides, going by the way it works, the natural computing system could be seen as a ``Bilateral Computing System''. We introduce the notion of Bilateral Computing in this paper, and we hope that this would lead to newer avenues of research in computing. The solution may be viewed as part of a more general type of natural computation called Bilateral Computing. The paper will also describe this new computing paradigm and will compare it with Reversible Computing. Our approach is informal: the emphasis is on motivation, ideas and implementation rather than a formal description.