  In this paper, we present a novel algorithm to solve the Boolean
Satisfiability (SAT) problem, using noise-based logic (NBL). Contrary to what
the name may suggest, NBL is not a random/fuzzy logic system. In fact, it is a
completely deterministic logic system. A key property of NBL is that it allows
us to apply a superposition of many input vectors to a SAT instance at the same
time, circumventing a key restriction and assumption in the traditional
approach to solving SAT. By exploiting the superposition property of NBL, our
NBL-based SAT algorithm can determine whether an instance is SAT or not in a
single operation. A satisfying solution can be found by iteratively performing
SAT check operations up to n times, where n is the number of variables in the
SAT instance. Although this paper does not focus on the realization of an
NBL-based SAT engine, such an engine can be conceived using analog circuits
(wide-band amplifiers, adders and multipliers), FPGAs or ASICs. Additionally,
we also discus scalability of our approach, which can apply to NBL in general.
The NBL-based SAT engine described in this paper has been simulated in software
for validation purposes.
