Boolean satisfiability using noise based logic
- Additional Document Info
- View All
Noise-based Logic (NBL) is a probabilistic logic system which can be used to simultaneously apply a superposition of arbitrarily many input vectors to a SAT instance. Using this property, we can determine whether an instance is SAT in a single operation. A satisfying solution can be found by iteratively performing SAT checks up to n times, where n is the number of variables in the SAT instance. In this paper, we formulate NBL-based SAT, and discuss its scalability. The NBL-based SAT engine has been simulated in software for validation purposes, although the focus of the paper is on the theory of NBL-based SAT. © 2012 ACM.
author list (cited authors)
Lin, P., Mandal, A., & Khatri, S. P.