论文标题
寻找比蛮力更快的满足分配：对布尔限制满意度的细粒度的观点
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction
论文作者
论文摘要
为了研究哪些情况下的问题可以比详尽的搜索（以及多少）更快地找到小解决方案，我们研究了布尔限制满意度与尺寸约束恰好$ k $的细粒度复杂性。更确切地说，我们旨在确定任何有限约束家庭，即最佳运行时间$ f（k）n^{g（k）} $，以找到令人满意的任务，以将$ n $变量的$ k $设置为$ 1 $。 在中心硬度假设上，关于图形和3均匀的超图中检测集团的假设，我们将$ g（k）$几乎紧密地描述为四个制度：（1）蛮力本质上是最好的，即$ g（k）=（k）=（1 \ pm o（1 \ pm o（1））k $，（1）k $，（2）当前的$ k $ - $ g（k）=（ω/3 \ pm o（1））k $，（3）指数对$ k $具有$ k $，in [ω（\ sqrt [3] {k}），o（\ sqrt {k}）\ in $ g（k）\ in [ω（\ sqrt [3] {k}），问题（\ sqrt {k}）$，或（4）问题是固定的，或$ g parce o（$ g）， 这比以前的FPT/W [1] - hADNESS二分法具有更细粒度的视角（Marx，计算复杂性2005）。我们最有趣的技术贡献是a $ f（k）n^{4 \ sqrt {k}} $ - 时间算法的子量算法，具有由目标$ k $的优先限制来参数（尤其是该方法），该方法是基于限制frobenius coin问题的限制，从而具有独立的利益。
To study the question under which circumstances small solutions can be found faster than by exhaustive search (and by how much), we study the fine-grained complexity of Boolean constraint satisfaction with size constraint exactly $k$. More precisely, we aim to determine, for any finite constraint family, the optimal running time $f(k)n^{g(k)}$ required to find satisfying assignments that set precisely $k$ of the $n$ variables to $1$. Under central hardness assumptions on detecting cliques in graphs and 3-uniform hypergraphs, we give an almost tight characterization of $g(k)$ into four regimes: (1) Brute force is essentially best-possible, i.e., $g(k) = (1\pm o(1))k$, (2) the best algorithms are as fast as current $k$-clique algorithms, i.e., $g(k)=(ω/3\pm o(1))k$, (3) the exponent has sublinear dependence on $k$ with $g(k) \in [Ω(\sqrt[3]{k}), O(\sqrt{k})]$, or (4) the problem is fixed-parameter tractable, i.e., $g(k) = O(1)$. This yields a more fine-grained perspective than a previous FPT/W[1]-hardness dichotomy (Marx, Computational Complexity 2005). Our most interesting technical contribution is a $f(k)n^{4\sqrt{k}}$-time algorithm for SubsetSum with precedence constraints parameterized by the target $k$ -- particularly the approach, based on generalizing a bound on the Frobenius coin problem to a setting with precedence constraints, might be of independent interest.
