Holographic algorithms

摘要

We introduce a new notion of efficient reduction among computational problems. Classical reductions involve gadgets that map local solutions of one problem to local solutions of another in one-to-one, or possibly many-to-one or one-to-many, fashion. Our proposed reductions allow for gadgets with many-to-many correspondences. Their objective is to preserve the sum of the local solutions. Such reductions provide a method of translating a combinatorial problem to a family of finite systems of polynomial equations with integer coefficients such that the number of solutions of the combinatorial problem can be counted in polynomial time if some system in the family has a solution over the complex numbers. We can derive polynomial time algorithms in this way for ten problems for which only exponential time algorithms were known before. General questions about complexity classes are also formulated. If the method is applied to a #P-complete problem then we obtain families of polynomial systems such that the solvability of any one member would imply P/sup #P/ = NC2.