Abstract.
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 Λk, where Λ 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 #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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper has been presented at AGACSE 2008 (3rd International Conference on Applied Geometric Algebras in Computer Science and Engineering).
Received: July 4, 2008. Accepted: October 1, 2008.
Rights and permissions
About this article
Cite this article
Schott, R., Stacey Staples, G. Reductions in Computational Complexity Using Clifford Algebras. AACA 20, 121–140 (2010). https://doi.org/10.1007/s00006-008-0143-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00006-008-0143-2