Generalized cofactors and decomposition of Boolean satisfiability problems [PDF]
CoRR, 2014 We propose an approach for decomposing Boolean satisfiability problems while extending recent results of \cite{sul2} on solving Boolean systems of equations. Developments in \cite{sul2} were aimed at the expansion of functions $f$ in orthonormal (ON) sets of base functions as a generalization of the Boole-Shannon expansion and the derivation of the ...
Madhav P. Desai, Virendra Sule
openalex +3 more sources
Generic hardness of the Boolean satisfiability problem
Groups, Complexity, Cryptology, 2017 AbstractIt follows from the famous result of Cook about the NP-completeness of the Boolean satisfiability problem that there is no polynomial algorithm for this problem ...
Alexander N Rybalov
exaly +5 more sources
Inverse Intersections for Boolean Satisfiability Problems [PDF]
CoRRBoolean Satisfiability (SAT) problems are expressed as mathematical formulas. This paper presents a matrix representation for these SAT problems. It shows how to use this matrix representation to get the full set of valid satisfying variable assignments.
Paul W. Homer
openalex +3 more sources
Projective cofactor decompositions of Boolean functions and the\n satisfiability problem [PDF]
CoRR, 2016 13 ...
Madhav Desai, Virendra Sule
openalex +3 more sources
A boolean satisfiability approach to the resource-constrained project scheduling problem [PDF]
Annals of Operations Research, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Andrei Horbach
openalex +3 more sources
The Satisfiability Problem for Boolean Set Theory with a Choice Correspondence [PDF]
Electronic Proceedings in Theoretical Computer Science, 2017 Given a set U of alternatives, a choice (correspondence) on U is a contractive map c defined on a family Omega of nonempty subsets of U. Semantically, a choice c associates to each menu A in Omega a nonempty subset c(A) of A comprising all elements of A
Domenico Cantone +2 more
doaj +6 more sources
Predicting the satisfiability of Boolean formulas by incorporating gated recurrent unit (GRU) in the Transformer framework [PDF]
PeerJ Computer ScienceThe Boolean satisfiability (SAT) problem exhibits different structural features in various domains. Neural network models can be used as more generalized algorithms that can be learned to solve specific problems based on different domain data than ...
Wenjing Chang, Mengyu Guo, Junwei Luo
doaj +3 more sources
Satisfiability problems and algebras of boolean constraint system games [PDF]
Illinois Journal of Mathematics, 2023 Fixed typos, reference added, and a few instances of mild rewording to improve ...
Connor Paddock, William Slofstra
openalex +3 more sources
Solving boolean satisfiability problems with the quantum approximate optimization algorithm [PDF]
PRX Quantum, 2022 One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers.
Sami Boulebnane, Ashley Montanaro
openalex +6 more sources
Solving the B-SAT Problem Using Quantum Computing: Smaller Is Sometimes Better [PDF]
EntropyThis paper aims to outline the effectiveness of modern universal gate quantum computers when utilizing different configurations to solve the B-SAT (Boolean satisfiability) problem.
Ahmad Bennakhi +2 more
doaj +2 more sources