Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-099 | 9th September 2005 00:00

Holographic Algorithms


Authors: Leslie G. Valiant
Publication: 13th September 2005 13:01
Downloads: 3452


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.

ISSN 1433-8092 | Imprint