On computational complexity of Clifford algebra

DOI10.1063/1.3133042MaRDI QIDQ3565282zbMATH OpenOpenAlexFDO

Authors Marco Budinich

Publication date 3 June 2010

Published in Journal of Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0904.0417

zbMATH Keywords

graph theorymatrix algebra

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Spinor and twistor methods applied to problems in quantum theory (81R25) Clifford algebras, spinors (15A66)

Abstract: After a brief discussion of the computational complexity of Clifford algebras, we present a new basis for even Clifford algebra Cl(2m) that simplifies greatly the actual calculations and, without resorting to the conventional matrix isomorphism formulation, obtains the same complexity. In the last part we apply these results to the Clifford algebra formulation of the NP-complete problem of the maximum clique of a graph introduced in a previous paper.

Recommendations

• Reductions in computational complexity using Clifford algebras
• Computational complexity reductions using Clifford algebras
• A spinorial formulation of the maximum clique problem of a graph
• Clifford algebra as a bridge between discrete and continuous worlds
• Computational complexity in algebraic systems

Cites work

• scientific article; zbMATH DE number 3091887 (Why is no real title available?)
• A spinorial formulation of the maximum clique problem of a graph
• Fock space description of simple spinors
• Gaussian elimination is not optimal
• On the algorithmic complexity of associative algebras

Cited in

(14)

• On spinors of zero nullity
• Spinorial formulations of graph problems
• Computational complexity reductions using Clifford algebras
• A theory of quantized fields based on orthogonal and symplectic Clifford algebras
• The extended Fock basis of Clifford algebra
• A spinorial formulation of the maximum clique problem of a graph
• Point particle with extrinsic curvature as a boundary of a Nambu-Goto string: classical and quantum model
• Generating functions of weighted voting games, MacMahon's partition analysis, and Clifford algebras
• On parallelizing the Clifford algebra product for \texttt{CLIFFORD}
• On Clifford algebras and binary integers
• Computations with Clifford and Grassmann algebras
• Clifford algebra method for network expression, computation, and algorithm construction
• On spinors transformations
• Reductions in computational complexity using Clifford algebras

This page was built for publication: On computational complexity of Clifford algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3565282)