Accelerating a continuous-time analog SAT solver using GPUs

DOI10.1016/J.CPC.2020.107469MaRDI QIDQ6040130zbMATH OpenOpenAlexFDO

Authors Ferenc Molnar, Shubha R. Kharel, Xiaobo Hu, Z. Toroczkai

Publication date 24 May 2023

Published in Computer Physics Communications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cpc.2020.107469

zbMATH Keywords

GPU accelerationNP-completenessBoolean satisfiabilitycontinuous-time algorithmRamsey number problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Coloring of graphs and hypergraphs (05C15) Numerical algorithms for specific classes of architectures (65Y10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Recommendations

• Simulating a P system based efficient solution to SAT by using GPUs
• Publication:5687266
• Scientific article; zbMATH DE number 2090309
• Anatomy and empirical evaluation of modern SAT solvers
• Publication:4475656

Cites work

• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 776267 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• scientific article; zbMATH DE number 236854 (Why is no real title available?)
• scientific article; zbMATH DE number 2192105 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• scientific article; zbMATH DE number 3375418 (Why is no real title available?)
• A family of embedded Runge-Kutta formulae
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Bioinformatics
• Complexity of protein folding
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Numerical Computations with GPUs
• OIM: oscillator-based Ising machines for solving combinatorial optimisation problems
• On the Ramsey numbers N(3,3,\dots ,3;2)
• SAT-solving in practice, with a tutorial example from supervisory control
• Some Practical Runge-Kutta Formulas
• Some theoretical challenges in digital geometry: a perspective
• Subgraph counting identities and Ramsey numbers
• The computational complexity of probabilistic inference using Bayesian belief networks
• The state of SAT

Cited in

(6)

• GPU-based acceleration of system-level design tasks
• Simulating a P system based efficient solution to SAT by using GPUs
• Accelerating numerical simulation of continuous-time Boolean satisfiability solver using discrete gradient
• Timescales of Boolean satisfiability solver using continuous-time dynamical system
• Random cyclic triangle-free graphs of prime order
• Correct Hardware Design and Verification Methods

This page was built for publication: Accelerating a continuous-time analog SAT solver using GPUs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6040130)