Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness
Jin‐Yi Cai, Pinyan Lu, Mingji Xia · 2008
We propose a new method to prove complexity dichotomy theorems. First we introduce Fibonacci gates which provide a new class of polynomial time holographic algorithms. Then we develop holographic reductions. We show that holographic reductions followed by interpolations provide a uniform strategy to prove #P-hardness.