论文标题
对采样SAT溶液的取代扩散
Denoising Diffusion for Sampling SAT Solutions
论文作者
论文摘要
为布尔值满意度问题（SAT）生成多种解决方案是一个严重的计算问题，用于测试和功能验证软件和硬件设计的实用应用。我们探索使用脱糖化扩散与图神经网络结合以实现去核功能的方式生成此类解决方案的方法。我们发现，所获得的精度类似于当前最佳的纯神经方法，即使对系统接受了来自标准求解器的非随机溶液的培训，所产生的SAT解决方案也非常多样化。
Generating diverse solutions to the Boolean Satisfiability Problem (SAT) is a hard computational problem with practical applications for testing and functional verification of software and hardware designs. We explore the way to generate such solutions using Denoising Diffusion coupled with a Graph Neural Network to implement the denoising function. We find that the obtained accuracy is similar to the currently best purely neural method and the produced SAT solutions are highly diverse, even if the system is trained with non-random solutions from a standard solver.
