Holographic Algorithms
DOI10.1137/070682575zbMath1152.05010MaRDI QIDQ3532577
Publication date: 28 October 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
computational complexity; enumeration; polynomial equations; polynomial time algorithms; complexity classes; holographic reduction; gadgets; efficient reduction; generating interference patterns; many-to-many correspondences; solution fragments
05A15: Exact enumeration problems, generating functions
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68W01: General topics in the theory of algorithms
Related Items