论文标题
关于2个满足性的多阶段视图
A Multistage View on 2-Satisfiability
论文作者
论文摘要
我们在多阶段模型中研究$ Q $ -SAT，重点是可解决的2个SAT。在此，给定$ q $ -cnf fomulas和一个非负整数$ d $的序列，问题是是否有一系列令人满意的真相分配，以至于每两个连续的真相分配，值更改的变量数量最多是$ d $。我们证明，即使在相当限制的情况下，多阶段2-SAT也是NP-HARD。此外，我们提出了用于多阶段2-SAT的参数化算法（包括内核化），并证明它们在渐近上是最佳的。
We study $q$-SAT in the multistage model, focusing on the linear-time solvable 2-SAT. Herein, given a sequence of $q$-CNF fomulas and a non-negative integer $d$, the question is whether there is a sequence of satisfying truth assignments such that for every two consecutive truth assignments, the number of variables whose values changed is at most $d$. We prove that Multistage 2-SAT is NP-hard even in quite restricted cases. Moreover, we present parameterized algorithms (including kernelization) for Multistage 2-SAT and prove them to be asymptotically optimal.
