We prove a complexity dichotomy theorem for a class of Holant problems on planar 3-regular bipartite graphs. The complexity dichotomy states that for every weighted constraint function $f$ defining the problem (the weights can even be negative), the problem is either computable in polynomial time if $f$ satisfies a tractability criterion, or \#P-hard otherwise. One particular problem in this problem space is a long-standing open problem of Moore and Robson on counting Cubic Planar X3C. The dichotomy resolves this problem by showing that it is \numP-hard. Our proof relies on the machinery of signature theory developed in the study of Holant problems. An essential ingredient in our proof of the main dichotomy theorem is a pure graph-theoretic result: Excepting some trivial cases, every 3-regular plane graph has a planar 3-way edge perfect matching. The proof technique of this graph-theoretic result is a combination of algebraic and combinatorial methods. The P-time tractability criterion of the dichotomy is explicit. Other than the known classes of tractable constraint functions (degenerate, affine, product type, matchgates-transformable) we also identify a new infinite set of P-time computable planar Holant problems; however, its tractability is not by a direct holographic transformation to matchgates, but by a combination of this method and a global argument. The complexity dichotomy states that everything else in this Holant class is \#P-hard.

翻译：我们证明了一个平面3-正则二分图Holant问题的复杂度二分定理。该复杂度二分定理指出，对于定义问题的加权限制函数$f$（权重甚至可以是负数），如果$f$满足可处理性准则，则问题可以在多项式时间内计算，否则可以归类为#P难。该问题空间中的一个特定问题是Moore和Robson关于计算Cubic Planar X3C的计数的一个长期未解之谜。该二分定理通过证明其为#P难来解决此问题。我们的证明依赖于开发Holant问题研究中的signature理论。证明上述主要二分定理的必要条件是一个纯图论结果：除了一些微不足道的情况外，每个3-正则平面图都有一个平面三元边完美匹配。这个图论结果的证明技巧是代数和组合方法的结合。该二分定理的P时间可处理性准则是显式的。除了已知的可计算的约束函数类别（退化、仿射、产品类型、匹配门可变换），我们还确定了一个新的无限可计算平面Holant问题集；但其可处理性不是通过直接到匹配门的全息变换，而是通过该方法和全局论证的组合。该复杂度二分定理指出，该Holant类别中的其他问题均为#P难。