We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Symmetry in SAT: an overview

Formal Metadata

Title
Symmetry in SAT: an overview
Alternative Title
Symmetry in SAT - a quest for pigeonhole
Title of Series
Number of Parts
28
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
Many a mathematical proof presents a symmetry argument to bypass an otherwise cumbersome case distinction. Similarly, combinatorial solvers can exploit symmetry to reduce the search space. This talk gives an overview of the techniques used in SAT solving to exploit symmetry properties of the problem at hand. It covers the topics of symmetry detection - typically via a transformation to graph automorphism though an argument for other approaches can be made; types of symmetry - different types have different needs; static and dynamic symmetry breaking - which remove symmetrical solutions from the solution set; symmetrical learning - which adds a symmetry rule to CDCL's proof system; and completeness of symmetry exploitation techniques - which arguably is the ultimate goal. The talk elaborates on the strengths and weaknesses of each technique, highlighting open questions and future research opportunities. As a common thread, we discuss the performance of each technique on the SAT encoding of the pigeonhole principle, which -in theory- can be decided in polynomial time using a symmetry argument. In practice however, efficiently deciding the SAT encoding of the pigeonhole principle remains a daunting challenge, as even after decades of research, none of the current techniques is able to fully detect and exploit the available symmetry.