Holographic Algorithm with Matchgates Is Universal for Planar $\#$CSP Over Boolean Domain

Jin-yi Cai, Zhiguo Fu

We prove a complexity classification theorem that classifies all counting constraint satisfaction problems ($\#$CSP) over Boolean variables into exactly three categories: (1) Polyn…