Holographic algorithms: From art to science

摘要

We develop the theory of holographic algorithms initiated by Leslie Valiant. First we define a basis manifold. Then we characterize algebraic varieties of realizable symmetric generators and recognizers on the basis manifold, and give a polynomial time decision algorithm for the simultaneous realizability problem. These results enable one to decide whether suitable signatures for a holographic algorithm are realizable, and if so, to find a suitable linear basis to realize these signatures by an efficient algorithm. Using the general machinery we are able to give unexpected holographic algorithms for some counting problems, modulo certain Mersenne type integers. These counting problems are #P-complete without the moduli. Going beyond symmetric signatures, we define d-admissibility and d-realizability for general signatures, and give a characterization of 2-admissibility and some general constructions of admissible and realizable families.