6 papers · 1 filter
Coloring Queens with Thousands of Encodings
Bernardo Subercaseaux, Benjamin Przybocki, Marijn J. H. Heule
In The Art of Computer Programming, Knuth benchmarked 10 encoding techniques for computing the chromatic number of the queen's graph: the minimum number of colors needed to color t…
Toward Satisfiability Modulo Realizability
Andrew Krapivin, Benjamin Przybocki, Marijn J. H. Heule
Problems complete for the existential theory of the reals () arise throughout discrete geometry. We introduce satisfiability modulo realizability, a SAT-based a…
Tao's Equational Proof Challenge Accepted (Technical Report)
Lydia Kondylidou, Jasmin Blanchette, Marijn J. H. Heule
In the context of the Equational Theories Project, Terence Tao posed the challenge of finding alternatives to a complicated 62-step proof found by the Vampire superposition prover.…
Doubly Saturated Ramsey Graphs: A Case Study in Computer-Assisted Mathematical Discovery
Benjamin Przybocki, John Mackey, Marijn J. H. Heule +1
Ramsey-good graphs are graphs that contain neither a clique of size nor an independent set of size . We study doubly saturated Ramsey-good graphs, defined as Ramsey-good gra…
Automated Reencoding Meets Graph Theory
Benjamin Przybocki, Bernardo Subercaseaux, Marijn J. H. Heule
Bounded Variable Addition (BVA) is a central preprocessing method in modern state-of-the-art SAT solvers. We provide a graph-theoretic characterization of which 2-CNF encodings can…
Orbitopal Fixing in SAT
Markus Anders, Cayden Codel, Marijn J. H. Heule
Despite their sophisticated heuristics, boolean satisfiability (SAT) solvers are still vulnerable to symmetry, causing them to visit search regions that are symmetric to ones alrea…