论文标题
二分法导致3个规则两分的非负功能
Dichotomy Result on 3-Regular Bipartite Non-negative Functions
论文作者
论文摘要
我们证明了在3型两分图上的一类Holant问题的复杂性二分法定理。给定一个任意的非负权对称约束功能$ f = [x_0，x_1，x_2，x_3] $，我们证明了两部分Holant问题$ \ operatatorName {holant} \ left（f \ mid p \ mid \ mid \ left（= _3 \ right） $ \＃$ p-hard。 $ F $上的二分法标准是明确的。
We prove a complexity dichotomy theorem for a class of Holant problems on 3-regular bipartite graphs. Given an arbitrary nonnegative weighted symmetric constraint function $f = [x_0, x_1, x_2, x_3]$, we prove that the bipartite Holant problem $\operatorname{Holant} \left( f \mid \left( =_3 \right) \right)$ is \emph{either} computable in polynomial time \emph{or} $\#$P-hard. The dichotomy criterion on $f$ is explicit.
