论文标题
复杂加权#CSP的指数时间复杂性
The Exponential-Time Complexity of the complex weighted #CSP
论文作者
论文摘要
在本文中，我认为在计数版本的指数时间假设（#eth）下，我考虑了布尔计数约束满意度问题（#CSP）的细粒度二分法（#CSP）。假设$ \ mathscr {f} $是布尔域上定义的代数复杂值功能的有限集。当$ \ mathscr {f} $是两个特殊函数集的子集时，我证明#csp（$ \ mathscr {f} $）是多项式时间可溶剂，否则不能在子指数时间内计算#ETH #ETH，除非#ETH失败。我还通过证明具有有界度的#CSP的相同二分法（每个变量在最恒定的约束下），即使对于＃r $ $ _3 $ -CSP，也可以改善结果。 在证明结果之前，一个重要的准备工作是争辩说，使用固定（两个特殊的Unary函数$ [1,0] $和$ [0,1] $用于减少Arity）也可以使Boolean #CSP问题的次指定下限保持。我通过利用一些常见方法来证明计数问题的＃p-智力来讨论这个问题。证明说明了这些常用方法之间的内部相关性。
In this paper, I consider a fine-grained dichotomy of Boolean counting constraint satisfaction problem (#CSP), under the exponential time hypothesis of counting version (#ETH). Suppose $\mathscr{F}$ is a finite set of algebraic complex-valued functions defined on Boolean domain. When $\mathscr{F}$ is a subset of either two special function sets, I prove that #CSP($\mathscr{F}$) is polynomial-time solvable, otherwise it can not be computed in sub-exponential time unless #ETH fails. I also improve the result by proving the same dichotomy holds for #CSP with bounded degree (every variable appears at most constant constraints), even for #R$_3$-CSP. An important preparation before proving the result is to argue that pinning (two special unary functions $[1,0]$ and $[0,1]$ are used to reduce arity) can also keep the sub-exponential lower bound of a Boolean #CSP problem. I discuss this issue by utilizing some common methods in proving #P-hardness of counting problems. The proof illustrates the internal correlation among these commonly used methods.
