Efficient Solution of Boolean Satisfiability Problems with Digital
MemComputing
- URL: http://arxiv.org/abs/2011.06551v1
- Date: Thu, 12 Nov 2020 18:13:46 GMT
- Title: Efficient Solution of Boolean Satisfiability Problems with Digital
MemComputing
- Authors: S.R.B. Bearden, Y.R. Pei, M. Di Ventra
- Abstract summary: We show that a memory-assisted physical system can efficiently solve the SAT problem in continuous time.
The efficiency of the simulations is related to the collective dynamical properties of the original physical system.
We anticipate our results to broaden research directions in physics-inspired computing paradigms.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 equations are integrated numerically, shows
evidence for polynomially-bounded scalability while solving "hard"
planted-solution instances of SAT, known to require exponential time to solve
in the typical case for both complete and incomplete algorithms. Furthermore,
we analytically demonstrate that the physical system can efficiently solve the
SAT problem in continuous time, without the need to introduce chaos or an
exponentially growing energy. The efficiency of the simulations is related to
the collective dynamical properties of the original physical system that
persist in the numerical integration to robustly guide the solution search even
in the presence of numerical errors. We anticipate our results to broaden
research directions in physics-inspired computing paradigms ranging from theory
to application, from simulation to hardware implementation.
Related papers
- NeuralStagger: Accelerating Physics-constrained Neural PDE Solver with
Spatial-temporal Decomposition [67.46012350241969]
This paper proposes a general acceleration methodology called NeuralStagger.
It decomposing the original learning tasks into several coarser-resolution subtasks.
We demonstrate the successful application of NeuralStagger on 2D and 3D fluid dynamics simulations.
arXiv Detail & Related papers (2023-02-20T19:36:52Z) - On Robust Numerical Solver for ODE via Self-Attention Mechanism [82.95493796476767]
We explore training efficient and robust AI-enhanced numerical solvers with a small data size by mitigating intrinsic noise disturbances.
We first analyze the ability of the self-attention mechanism to regulate noise in supervised learning and then propose a simple-yet-effective numerical solver, Attr, which introduces an additive self-attention mechanism to the numerical solution of differential equations.
arXiv Detail & Related papers (2023-02-05T01:39:21Z) - Solving Subset Sum Problems using Quantum Inspired Optimization
Algorithms with Applications in Auditing and Financial Data Analysis [2.0981723008692392]
We show how gradient descent on Hopfield Networks reliably finds solutions for both artificial and real data.
We outline how this algorithm can be applied by adiabatic quantum computers.
arXiv Detail & Related papers (2022-10-28T12:22:15Z) - Message Passing Neural PDE Solvers [60.77761603258397]
We build a neural message passing solver, replacing allally designed components in the graph with backprop-optimized neural function approximators.
We show that neural message passing solvers representationally contain some classical methods, such as finite differences, finite volumes, and WENO schemes.
We validate our method on various fluid-like flow problems, demonstrating fast, stable, and accurate performance across different domain topologies, equation parameters, discretizations, etc., in 1D and 2D.
arXiv Detail & Related papers (2022-02-07T17:47:46Z) - Towards algorithm-free physical equilibrium model of computing [0.0]
A new model of computing is proposed to replace the sequential paradigm of algorithms with inherent parallelism of physical processes.
We construct physical systems whose equilibrium states correspond to the desired solutions and let them evolve to search for the solutions.
The main requirements of the model are identified and quantum circuits are proposed for its potential implementation.
arXiv Detail & Related papers (2021-11-30T09:48:39Z) - Probabilistic ODE Solutions in Millions of Dimensions [19.09929271850469]
We explain the mathematical assumptions and detailed implementation schemes behind solving high-dimensional ODEs with a probabilistic numerical algorithm.
This has not been possible before due to matrix-matrix operations in each solver step.
We evaluate the resulting efficiency on a range of problems, including the probabilistic numerical simulation of a differential equation with millions of dimensions.
arXiv Detail & Related papers (2021-10-22T14:35:45Z) - Transformer-based Machine Learning for Fast SAT Solvers and Logic
Synthesis [63.53283025435107]
CNF-based SAT and MaxSAT solvers are central to logic synthesis and verification systems.
In this work, we propose a one-shot model derived from the Transformer architecture to solve the MaxSAT problem.
arXiv Detail & Related papers (2021-07-15T04:47:35Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure.
We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
arXiv Detail & Related papers (2021-06-09T08:05:36Z) - Directed percolation and numerical stability of simulations of digital
memcomputing machines [8.761355402590105]
Digital memcomputing machines (DMMs) are a novel, non-solving class of machines designed to solve optimization problems.
These machines can be physically realized with continuous-time, non-quantum dynamical systems with memory.
Solutions of many hard problems have been reported by numerically integrating the ODEs of DMMs.
arXiv Detail & Related papers (2021-02-06T09:44:28Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - Stable Implementation of Probabilistic ODE Solvers [27.70274403550477]
Probabilistic solvers for ordinary differential equations (ODEs) provide efficient quantification of numerical uncertainty.
They suffer from numerical instability when run at high order or with small step-sizes.
The present work proposes and examines a solution to this problem.
It involves three components: accurate initialisation, a coordinate change preconditioner that makes numerical stability concerns step-size-independent, and square-root implementation.
arXiv Detail & Related papers (2020-12-18T08:35:36Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.