The Boolean satisfiability problem in Clifford algebra

DOI10.1016/J.TCS.2019.03.027zbMATH Open1423.68438arXiv1704.02942OpenAlexW2606159282MaRDI QIDQ2317865FDOQ2317865

Authors: Marco Budinich 

Publication date: 13 August 2019

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

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.

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

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

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)

Cites Work

• The complexity of theorem-proving procedures
• Title not available (Why is that?)
• Title not available (Why is that?)
• An improved exponential-time algorithm for k -SAT
• Title not available (Why is that?)
• Survey propagation: An algorithm for satisfiability
• Zeons, orthozeons, and graph colorings
• On spinors transformations

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)