TR05-099 Authors: Leslie G. Valiant

Publication: 13th September 2005 13:01

Downloads: 3452

Keywords:

Complexity theory is built fundamentally on the notion of efficient

reduction among computational problems. Classical

reductions involve gadgets that map solution fragments of one problem to

solution fragments of another in one-to-one, or

possibly one-to-many, fashion. In this paper we propose a new kind of

reduction that allows for gadgets with many-to-many

correspondences, in which the individual correspondences among the

solution fragments can no longer be identified. Their objective

may be viewed as that of generating interference patterns among

these solution fragments so as to conserve their sum.

We show that such holographic 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 derive polynomial time algorithms in this way for a number of problems for

which only exponential time algorithms were known before.

General questions about complexity classes can also be formulated. If the method is

applied to a #P-complete problem then a family of polynomial systems is obtained such

that the solvability of any one member would imply that #P can be computed within NC2.