Theory and Applications of Satisfiability Testing - SAT 2012
Theory and Applications of Satisfiability Testing - SAT 2012
复制标题
满意度测试的理论与应用 - SAT 2012
DOI：
10.1007/978-3-642-31612-8_26
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Creignou N
中科院分区：
文献类型：
--
作者：
Creignou N
我们考虑布尔电路和命题公式的加权可满足性问题，其中赋值的权重是设置为 true 的变量数量。我们研究这些问题的参数化复杂性，并对其片段的复杂性进行系统研究。到目前为止，仅考虑了单调片段，并证明其与无限制问题具有相同的复杂性。在这里，我们认为通过语义限制电路或公式获得的所有片段仅包含来自固定 setBof 布尔函数的门（连接词）。我们通过证明对于每个这样的 B，加权可满足性问题是 W[P]-完全（对于电路）或 W[SAT]-完全（对于公式）或可有效解决来获得二分结果。我们还考虑了相关的计数问题。
We consider the weighted satisfiability problem for Boolean circuits and propositional formulæ, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these problems and initiate a systematic study of the complexity of its fragments. Only the monotone fragment has been considered so far and proven to be of same complexity as the unrestricted problems. Here, we consider all fragments obtained by semantically restricting circuits or formulæ to contain only gates (connectives) from a fixed setBof Boolean functions. We obtain a dichotomy result by showing that for each suchB, the weighted satisfiability problems are either W[P]-complete (for circuits) or W[SAT]-complete (for formulæ) or efficiently solvable. We also consider the related counting problems.