A review of the literature on local search algorithms for MAX-SAT
A review of the literature on local search algorithms for MAX-SAT
复制标题
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
T. Stützle;H. Hoos;A. Roli
中科院分区：
文献类型：
--
作者：
T. Stützle;H. Hoos;A. Roli
命题逻辑中的可满足性问题（SAT）是指对于一个给定的命题公式，判定它是否有一个模型的任务。这个问题在计算机科学的各个领域、数理逻辑和人工智能中都起着重要作用，而且在诸如异步电路综合[29]、归纳推理[41]、数据库完整性[3]、硬件验证以及许多其他应用中也是如此。SAT也是第一个被证明为完备的问题[11]，因此它是理论计算机科学的核心问题之一。
The satisfiability problem in propositional logic (SAT) is the task to decide for a given propositional formula whether it has a model. This problem plays a prominent role in various areas of computer science, mathematical logic and artificial intelligence, but also in applications such as asynchronous circuit synthesis [29], inductive inference [41], integrity of databases [3], hardware verification and many others. SAT was also the first problem to be proven complete [11] and as such is amongst the central problems in theoretical computer science.