Holographic algorithm
Encyclopedia
In computer science
, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a reduction
that preserves the number of solutions. These concepts were introduced by Leslie Valiant
and are a natural type of reduction for #P
problems.
Holographic algorithms can obtain exponential speedup on certain classes of problems. They have received notable coverage due to speculation that they are relevant to the P versus NP problem and their impact on computational complexity theory
.
The algorithms are unrelated to laser holography
, except metaphorically. Their power comes from the mutual cancellation of many contributions to a sum, analogous to the interference patterns in a hologram. Holographic algorithms have some similarities with quantum computation, but they use classical computation.
of sets of problems, and reduction to perfect matching problems.
The number of perfect matchings in a planar graph
can be computed in polynomial time by using the FKT algorithm
, dating to the 1960s.
The FKT algorithm converts the problem into a Pfaffian
computation, which can be solved polynomially using standard determinant
algorithms. Note that although the basic formula for the determinant contains n!
terms, the structure of the determinant allows it to be computed in polynomial time, as many terms cancel out and don't need to be computed. This cancellation is a key to holographic algorithms.
The second concept in holographic algorithms is reducing a problem to a different problem via holographic reduction. A standard technique in complexity is many-one reduction
, so an instance of a problem is reduced to an instance of a (hopefully simpler) problem.
However, holographic reductions between two computational problems preserve the sum of solutions without preserving correspondences between solutions. For instance, the total number of solutions in both sets can be preserved, even though individual problems don't have matching solutions. The sum can also be weighted, rather than simply counting the number of solutions, using linear basis vectors
.
The holographic reduction uses matchgates, which are graph-theoretic entities, analogous to logic gate
s, that use perfect matching to perform operations. The matchgates are combined into a planar graph called a matchgrid. By Valiant's Holant Theorem, the (polynomial-time) perfect matching algorithm gives the solution to the matchgrid problem. Thus, the original problem is solved in polynomial time.
solutions to problems without formerly-known polynomial solutions in satisfiability
, vertex cover
, and other graph problems
. Although some of these problems are related to NP-complete
problems, they are not themselves NP-complete, and thus do not prove P=NP. Also, some of the solved problems are argued to be contrived (such as '#7
Pl
-Rtw-Mon-3CNF
').
A key research area is extending holographic algorithms to new problems.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a reduction
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....
that preserves the number of solutions. These concepts were introduced by Leslie Valiant
Leslie Valiant
Leslie Gabriel Valiant is a British computer scientist and computational theorist.He was educated at King's College, Cambridge, Imperial College London, and University of Warwick where he received his Ph.D. in computer science in 1974. He started teaching at Harvard University in 1982 and is...
and are a natural type of reduction for #P
Sharp-P
In computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ƒ," where ƒ is the number of accepting paths of a nondeterministic...
problems.
Holographic algorithms can obtain exponential speedup on certain classes of problems. They have received notable coverage due to speculation that they are relevant to the P versus NP problem and their impact on computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
.
The algorithms are unrelated to laser holography
Holography
Holography is a technique that allows the light scattered from an object to be recorded and later reconstructed so that when an imaging system is placed in the reconstructed beam, an image of the object will be seen even when the object is no longer present...
, except metaphorically. Their power comes from the mutual cancellation of many contributions to a sum, analogous to the interference patterns in a hologram. Holographic algorithms have some similarities with quantum computation, but they use classical computation.
How the algorithms work
The algorithms are based on several concepts: counting perfect matchings, holographic reductionReduction (complexity)
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....
of sets of problems, and reduction to perfect matching problems.
The number of perfect matchings in a planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
can be computed in polynomial time by using the FKT algorithm
FKT algorithm
The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. Counting the number of matchings, even for planar graphs, is also #P-complete...
, dating to the 1960s.
The FKT algorithm converts the problem into a Pfaffian
Pfaffian
In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries. This polynomial is called the Pfaffian of the matrix, The term Pfaffian was introduced by who named them after Johann Friedrich Pfaff...
computation, which can be solved polynomially using standard determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
algorithms. Note that although the basic formula for the determinant contains n!
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
terms, the structure of the determinant allows it to be computed in polynomial time, as many terms cancel out and don't need to be computed. This cancellation is a key to holographic algorithms.
The second concept in holographic algorithms is reducing a problem to a different problem via holographic reduction. A standard technique in complexity is many-one reduction
Many-one reduction
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
, so an instance of a problem is reduced to an instance of a (hopefully simpler) problem.
However, holographic reductions between two computational problems preserve the sum of solutions without preserving correspondences between solutions. For instance, the total number of solutions in both sets can be preserved, even though individual problems don't have matching solutions. The sum can also be weighted, rather than simply counting the number of solutions, using linear basis vectors
Basis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
.
The holographic reduction uses matchgates, which are graph-theoretic entities, analogous to logic gate
Logic gate
A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and...
s, that use perfect matching to perform operations. The matchgates are combined into a planar graph called a matchgrid. By Valiant's Holant Theorem, the (polynomial-time) perfect matching algorithm gives the solution to the matchgrid problem. Thus, the original problem is solved in polynomial time.
Research
Holographic algorithms have been used to find polynomialP (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
solutions to problems without formerly-known polynomial solutions in satisfiability
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
, vertex cover
Vertex cover
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
, and other graph problems
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
. Although some of these problems are related to NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problems, they are not themselves NP-complete, and thus do not prove P=NP. Also, some of the solved problems are argued to be contrived (such as '#7
Modulo operation
In computing, the modulo operation finds the remainder of division of one number by another.Given two positive numbers, and , a modulo n can be thought of as the remainder, on division of a by n...
Pl
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
-Rtw-Mon-3CNF
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
').
A key research area is extending holographic algorithms to new problems.