pith. sign in

arxiv: 2110.01173 · v1 · pith:2B4352HMnew · submitted 2021-10-04 · 💻 cs.CC

Bipartite 3-Regular Counting Problems with Mixed Signs

classification 💻 cs.CC
keywords holantleftproblemsrightbipartitecomputableconstraintcounting
0
0 comments X
read the original abstract

We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. For every problem of the form $\operatorname{Holant}\left(f\mid =_3 \right)$, where $f$ is any integer-valued ternary symmetric constraint function on Boolean variables, we prove that it is either P-time computable or #P-hard, depending on an explicit criterion of $f$. The constraint function can take both positive and negative values, allowing for cancellations. The dichotomy extends easily to rational valued functions of the same type. In addition, we discover a new phenomenon: there is a set $\mathcal{F}$ with the property that for every $f \in \mathcal{F}$ the problem $\operatorname{Holant}\left(f\mid =_3 \right)$ is planar P-time computable but #P-hard in general, yet its planar tractability is by a combination of a holographic transformation by $\left[\begin{smallmatrix} 1 & 1 \\ 1 & -1 \end{smallmatrix}\right]$ to FKT together with an independent global argument.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.