pith. sign in

arxiv: 2011.09110 · v1 · pith:L534OG3Xnew · submitted 2020-11-18 · 💻 cs.CC

Dichotomy Result on 3-Regular Bipartite Non-negative Functions

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

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.

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.