2025/05/28 by Yihan He, Ming‐Chun Hong, He, Yihan +16
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Physics (physics.comp-ph) #FOS: Physical sciences #Formal Methods in Verification #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2505.22215
openalex publication_date 2025/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Boolean Satisfiability (SAT) problems are critical in fields such as artificial intelligence and cryptography, where efficient solutions are essential. Conventional probabilistic solvers often encounter scalability issues due to complex logic synthesis steps. In this work, we present a novel approach for solving the 3-SAT Boolean satisfiability problem using hypergraph-based probabilistic computers obtained through direct mapping. This method directly translates 3-SAT logical expressions into hypergraph structures, thereby circumventing conventional logic decomposition and synthesis procedures, and offering a more streamlined solver architecture. For representative uf100-430 instances, the proposed approach reduces the node count from 631 to 100 and the edge count from ~2,423 to ~1,013. Under identical simulated annealing conditions, the conventional simple undirected graph (SUG)-based solver achieves a 0% success rate across the tested instances, whereas the hypergraph-based solver attains an average success rate of ~77.6%. In addition, the hypergraph-based method reaches an average minimum energy of ~0.24, close to the theoretical ground state, while the SUG-based architecture remains trapped at substantially higher energy levels (~9.12 on average). The direct hypergraph mapping can further be extended to k-SAT formulations, providing a scalable framework for more complex satisfiability problems in probabilistic computing.