Reductions in computational complexity using Clifford algebras

DOI10.1007/s00006-008-0143-2zbMath1191.68335MaRDI QIDQ964729

René Schott, George Stacey Staples

Publication date: 20 April 2010

Published in: Advances in Applied Clifford Algebras (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00006-008-0143-2

zbMATH Keywords

Hamiltonian cycles; NP-hard; set covering problem; travelling salesman problem; NP-complete; quantum computing; longest path; set packing problem; cycle cover; matrix permanent

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

81P68: Quantum computation

05C38: Paths and cycles

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

60B99: Probability theory on algebraic and topological structures

Uses Software

• CLIFFORD
• Gaigen
• Cliffosor