Dichotomy for Real Holant$^c$ Problems

Understand

Holant problems capture a class of Sum-of-Product computations such as counting matchings.

• It is inspired by holographic algorithms and is equivalent to tensor networks, with counting CSP being a special case.
• A classification for Holant problems is more difficult to prove, not only because it implies a classification for counting CSP, but also due to the deeper reason that there exist more intricate polynomial time tractable problems in the broader framework.
• We discover a new family of constraint functions $\mathscr{L}$ which define polynomial time computable counting problems.