Efficient solution of Boolean satisfiability problems with digital memcomputing.

ABSTRACT: Boolean satisfiability is a propositional logic problem of interest in multiple fields, e.g., physics, mathematics, and computer science. Beyond a field of research, instances of the SAT problem, as it is known, require efficient solution methods in a variety of applications. It is the decision problem of determining whether a Boolean formula has a satisfying assignment, believed to require exponentially growing time for an algorithm to solve for the worst-case instances. Yet, the efficient solution of many classes of Boolean formulae eludes even the most successful algorithms, not only for the worst-case scenarios, but also for typical-case instances. Here, we introduce a memory-assisted physical system (a digital memcomputing machine) that, when its non-linear ordinary differential equat

SUBMITTER: Bearden SRB 

PROVIDER: S-EPMC7665037 | biostudies-literature | 2020 Nov

REPOSITORIES: biostudies-literature