Invention Grant
- Patent Title: Method of constructing dynamical systems for solving Boolean satisfiability
-
Application No.: US15890197Application Date: 2018-02-06
-
Publication No.: US10732971B1Publication Date: 2020-08-04
- Inventor: Andrew Pomerance
- Applicant: Andrew Pomerance
- Agent Krishna Kalidindi
- Main IPC: G06F30/00
- IPC: G06F30/00 ; G06F9/30 ; G06F17/11 ; G06F16/33

Abstract:
A method for generating dynamical systems that can be instantiated on reconfigurable computing platforms for solving instances of the Boolean satisfiability problem (SAT) is disclosed. When the SAT instance can be satisfied by an appropriate assignment of the variables, the dynamical system has a fixed point attractor that corresponds to a satisfying assignment of variables. When the SAT instance cannot be satisfied by any assignment of variables, there is no such fixed point attractor. Exemplary embodiments represent a physically-realizable computing device that solves SAT problems outside the Turing machine paradigm. Exemplary embodiments detect when the system reaches a fixed point attractor.
Information query