Holographic algorithm
In computer science, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a constant-time reduction that maps solution fragments many-to-many such that the sum of the solution fragments remains unchanged. These concepts were introduced by Leslie Valiant, who called them holographic because "their effect can be viewed as that of producing interference patterns among the solution fragments". 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.
- Comment
- enIn computer science, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a constant-time reduction that maps solution fragments many-to-many such that the sum of the solution fragments remains unchanged. These concepts were introduced by Leslie Valiant, who called them holographic because "their effect can be viewed as that of producing interference patterns among the solution fragments". 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.
- Has abstract
- enIn computer science, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a constant-time reduction that maps solution fragments many-to-many such that the sum of the solution fragments remains unchanged. These concepts were introduced by Leslie Valiant, who called them holographic because "their effect can be viewed as that of producing interference patterns among the solution fragments". 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 been used to find polynomial-time solutions to problems without such previously known solutions for special cases of satisfiability, vertex cover, and other graph 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. Although some of the general problems are #P-hard problems, the special cases solved are not themselves #P-hard, and thus do not prove FP = #P. Holographic algorithms have some similarities with quantum computation, but are completely classical.
- Hypernym
- Algorithm
- Is primary topic of
- Holographic algorithm
- Label
- enHolographic algorithm
- Link from a Wikipage to another Wikipage
- Basis (linear algebra)
- Bipartite graph
- Boolean satisfiability problem
- Category:Algorithms
- Chinese remainder theorem
- Complement (set theory)
- Computational complexity theory
- Computer science
- Conjunctive normal form
- Constraint graph
- Constraint satisfaction problem
- Fibonacci number
- FKT algorithm
- Graph theory
- Holography
- Hypergraph
- Independent set (graph theory)
- Invertible matrix
- Leslie Valiant
- Many-one reduction
- Matchgates
- Mersenne number
- Modular arithmetic
- Modulo operation
- Monotonic function
- P (complexity)
- Perfect matching
- Planar graph
- P versus NP problem
- Quantum computation
- Recurrence relation
- Reduction (complexity)
- Regular graph
- Sharp-P
- Symmetric function
- Tensor product
- Truth table
- Vertex cover
- SameAs
- 4mtWC
- Holographic algorithm
- Holographic algorithm
- m.03d9ftl
- Q5884100
- Subject
- Category:Algorithms
- WasDerivedFrom
- Holographic algorithm?oldid=1078634098&ns=0
- WikiPageLength
- 14302
- Wikipage page ID
- 14609233
- Wikipage revision ID
- 1078634098
- WikiPageUsesTemplate
- Template:For
- Template:Reflist