SESSION 25 High Concepts at High Frequencies.pdf

1、ISSCC 2025SESSION 25High Concepts at High Frequencies25.1:A Physics-Inspired Oscillator-Based Mixed-Signal Optimization Engine for Solving 50-Variable 218-Clause 3-SAT Problems with 100%Solvability and 31.7s Solution Time 2025 IEEE International Solid-State Circuits Conference1 of 42A Physics-Inspir

2、ed Oscillator-Based Mixed-Signal Optimization Engine for Solving 50-Variable 218-Clause 3-SAT Problems with 100%Solvability and 31.7s Solution TimeEvangelos Dikopoulos,Ying-Tuan Hsu*,Luke Wormald*,Wei Tang,Zhengya Zhang,Michael P.FlynnUniversity of Michigan,EECS Dept.Email:vangelisumich.edu25.1:A Ph

3、ysics-Inspired Oscillator-Based Mixed-Signal Optimization Engine for Solving 50-Variable 218-Clause 3-SAT Problems with 100%Solvability and 31.7s Solution Time 2025 IEEE International Solid-State Circuits Conference2 of 42Boolean Satisfiability(SAT)Find assignments to N Boolean variables XN=x1,x2,xN

4、 that satisfy a given Boolean formula:F(X)=1Clause3-SAT Single Clause ExampleF=(X89or(not X92)or X36)and Solution:X89,X92,X36=0,0,025.1:A Physics-Inspired Oscillator-Based Mixed-Signal Optimization Engine for Solving 50-Variable 218-Clause 3-SAT Problems with 100%Solvability and 31.7s Solution Time

5、2025 IEEE International Solid-State Circuits Conference3 of 42Boolean Satisfiability(SAT)3-SAT ExampleF=(X89 X92 X36)(X10 X31 X40)(X21 X65 X89)or ,not ,and Clause 1Clause 0Clause MFind assignments to N Boolean variables XN=x1,x2,xN that satisfy a given Boolean formula:F(X)=125.1:A Physics-Inspired O

6、scillator-Based Mixed-Signal Optimization Engine for Solving 50-Variable 218-Clause 3-SAT Problems with 100%Solvability and 31.7s Solution Time 2025 IEEE International Solid-State Circuits Conference4 of 42Applications of SATSolver01011101010SAT SolutionAICryptoEDAHealth-careComp.BioDefenseLogistics