A Physics-Inspired Oscillator-Based Mixed-Signal Optimization Engine for Solving 50-Variable 218-Clause 3-SAT Problems with 100% Solvability and 31.7μs Solution Time

📋 论文概要

本文提出一种基于振荡器的混合信号优化引擎，用于解决50变量218子句的3-SAT问题。该物理启发计算机利用连续时间操作和大规模并行性，通过将优化目标映射到自旋动力系统来提高求解效率。

💡 主要创新点

• 采用振荡器阵列实现混合信号连续时间操作，提供大规模并行计算能力
• 将布尔可满足性问题映射到物理启发自旋系统，实现高效NP完全问题求解

🏷 关键词

📄 原文摘要

Zhengya Zhang, Michael P. Flynn University of Michigan, Ann Arbor, MI *Equally Credited Authors (ECAs) The Boolean satisfiability (SAT) problem is a fundamental NP-complete problem, and efficiently solving it would revolutionize fields like optimization, artificial intelligence, cryptography, software, and hardware verification. Physics-inspired computers offer significant advantages, including continuous-time (CT) operation, massive parallelism, and increased energy efficiency. Solvers that map the optimization objective to a dynamical system of spins [1] have been shown to outperform classical discrete optimization solvers. Recent work maps 3-SAT to systems of coupled spins but suffers from long solution times or low solvability [2,3], and is limited to problems with only 20 variables [3]. [4] decomposes 3-SAT problems to an all-to-all connected analog Ising machine, but the proposed iterative compute scheme results in ms-level solution times. A digital solver based

👥 作者与机构

Evangelos Dikopoulos, Ying-Tuan Hsu*, Luke Wormald*, Wei Tang,