ECCC-Report TR05-099https://eccc.weizmann.ac.il/report/2005/099Comments and Revisions published for TR05-099en-usTue, 13 Sep 2005 13:01:59 +0300
Paper TR05-099
| Holographic Algorithms |
Leslie G. Valiant
https://eccc.weizmann.ac.il/report/2005/099Complexity 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.
Tue, 13 Sep 2005 13:01:59 +0300https://eccc.weizmann.ac.il/report/2005/099