Wijesinghe Parami, Liyanagedera Chamika, Roy Kaushik
Purdue University, School of Electrical and Computer Engineering, West Lafayette, Indiana, 47907, USA.
Sci Rep. 2018 May 2;8(1):6940. doi: 10.1038/s41598-018-24877-z.
Boolean satisfiability (k-SAT) is an NP-complete (k ≥ 3) problem that constitute one of the hardest classes of constraint satisfaction problems. In this work, we provide a proof of concept hardware based analog k-SAT solver, that is built using Magnetic Tunnel Junctions (MTJs). The inherent physics of MTJs, enhanced by device level modifications, is harnessed here to emulate the intricate dynamics of an analog satisfiability (SAT) solver. In the presence of thermal noise, the MTJ based system can successfully solve Boolean satisfiability problems. Most importantly, our results exhibit that, the proposed MTJ based hardware SAT solver is capable of finding a solution to a significant fraction (at least 85%) of hard 3-SAT problems, within a time that has a polynomial relationship with the number of variables(<50).
布尔可满足性问题（k-SAT）是一个NP完全问题（k≥3），是最难的约束满足问题类别之一。在这项工作中，我们提供了一种基于概念验证硬件的模拟k-SAT求解器，它是使用磁性隧道结（MTJ）构建的。这里利用MTJ的固有物理特性，并通过器件级修改加以增强，来模拟模拟可满足性（SAT）求解器的复杂动态。在存在热噪声的情况下，基于MTJ的系统能够成功解决布尔可满足性问题。最重要的是，我们的结果表明，所提出的基于MTJ的硬件SAT求解器能够在与变量数量（<50）呈多项式关系的时间内，找到相当一部分（至少85%）的难解3-SAT问题的解。
