The Boolean satisfiability problem in Clifford algebra

DOI10.1016/J.TCS.2019.03.027MaRDI QIDQ2317865zbMATH OpenOpenAlexFDO

Authors Marco Budinich

Publication date 13 August 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

satisfiabilityClifford algebrageometric algebra

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40) Clifford algebras, spinors (15A66)

Abstract: We present a formulation of the Boolean Satisfiability Problem in spinor language that allows to give a necessary and sufficient condition for unsatisfiability. With this result we outline an algorithm to test for unsatisfiability with possibly interesting theoretical properties.

Recommendations

• Zeon and idem-Clifford formulations of Boolean satisfiability
• scientific article; zbMATH DE number 7300404
• A numerical approach to 3-SAT
• Solving satisfiability in less than \(2^ n\) steps
• An algorithm for the satisfiability problem of formulas in conjunctive normal form

Cites work

• scientific article; zbMATH DE number 3909745 (Why is no real title available?)
• scientific article; zbMATH DE number 813122 (Why is no real title available?)
• scientific article; zbMATH DE number 3091887 (Why is no real title available?)
• An improved exponential-time algorithm for k -SAT
• On spinors transformations
• Survey propagation: An algorithm for satisfiability
• The complexity of theorem-proving procedures
• Zeons, orthozeons, and graph colorings

Cited in

(2)

• Clifford algebra as a bridge between discrete and continuous worlds
• Zeon and idem-Clifford formulations of Boolean satisfiability

This page was built for publication: The Boolean satisfiability problem in Clifford algebra

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