Boolean satisfiability using noise based logic Conference Paper uri icon

abstract

  • 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.

citation count

  • 4

publication date

  • July 2012