Holographic reduction, interpolation and hardness
We introduce the method of proving complexity dichotomy theorems by holographic reductions. Combined with interpolation, we present a unified strategy to prove #P-hardness. Specifically, we prove a complexity dichotomy theorem for a class of counting problems on 2-3 regular graphs expressible by Boolean signatures. For these problems, whenever a holographic reduction followed by interpolation fails to prove #P-hardness, we can show that the problem is solvable in polynomial time.
holographic reduction #p-hard polynomial interpolation counting complexity