Schott, René; Staples, G. Stacey Reductions in computational complexity using Clifford algebras. (English) Zbl 1191.68335 Adv. Appl. Clifford Algebr. 20, No. 1, 121-140 (2010). Summary: A number of combinatorial problems are treated using properties of abelian null-square-generated and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of \(\Lambda^{k}\), where \(\Lambda\) is an appropriate nilpotent adjacency matrix, the \(k\)-cycles in any finite graph are recovered. Within the algebra context (i.e., considering the number of multiplications performed within the algebra), these problems are reduced to matrix multiplication, which is in complexity class P. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and \(\sharp\)P-complete to class P in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph. Cited in 9 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C38 Paths and cycles 60B99 Probability theory on algebraic and topological structures 81P68 Quantum computation 68R10 Graph theory (including graph drawing) in computer science Keywords:Hamiltonian cycles; travelling salesman problem; longest path; NP-hard; NP-complete; cycle cover; set packing problem; set covering problem; matrix permanent; quantum computing Software:Cliffosor; Gaigen; CLIFFORD PDFBibTeX XMLCite \textit{R. Schott} and \textit{G. S. Staples}, Adv. Appl. Clifford Algebr. 20, No. 1, 121--140 (2010; Zbl 1191.68335) Full Text: DOI HAL