On computational complexity of Clifford algebra

DOI10.1063/1.3133042zbMATH Open1187.15025arXiv0904.0417OpenAlexW3103115337MaRDI QIDQ3565282FDOQ3565282

Authors: Marco Budinich 

Publication date: 3 June 2010

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

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.

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

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

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)

Cites Work

• Gaussian elimination is not optimal
• Fock space description of simple spinors
• Title not available (Why is that?)
• A spinorial formulation of the maximum clique problem of a graph
• On the algorithmic complexity of associative algebras

Cited In (13)

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