ABSTRACT
The term holographic reduction was coined by Leslie Valiant. A holographic reduction is a many-to-many mapping between two finite sets, such that the sum of the fragments of elements in one set is mapped onto the sum of the fragments of elements in another set. However, the mapping is such that it proves the equality between the cardinality of the two sets. When the two sets are the solutions of problem instances in two different counting problems, the holographic reduction can prove that the two counting problems have the same computational complexity. If one of the problems can be solved in polynomial time, so can the other problem be solved. Similarly, the #P-completeness of one of the problems proves the #P-completeness of the other problem.
