Boolean Satisfiability using Noise Based Logic

Details Boolean Satisfiability using Noise Based Logic Boolean Satisfiability using Noise Based Logic

2011-10-04

arxiv.org/abs/1110.0550v1

Computer Science

Computational Complexity

6 pages, 1 figure

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Boolean Satisfiability using Noise Based Logic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Boolean Satisfiability using Noise Based Logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boolean Satisfiability using Noise Based Logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-267497