Next: Exploiting symmetry without changing Up: Generalizing Boolean Satisfiability I: Previous: Summary

# Symmetry

Given that the pigeonhole problem and clique-coloring problems involve a great deal of symmetry in their arguments, a variety of authors have suggested extending Boolean representation or inference in a way that allows this symmetry to be exploited directly. We will discuss the variety of approaches that have been proposed by separating them based on whether or not a modification to the basic resolution inference rule is suggested. In any event, we make the following definition:

Definition 4.1   Let be a collection of axioms. By a symmetry of we will mean any permutation of the variables in that leaves itself unchanged.

As an example, if consists of the single axiom , then is clearly symmetric under the exchange of and . If contains the two axioms

and

then is once again symmetric under the exchange of and .

Subsections

Next: Exploiting symmetry without changing Up: Generalizing Boolean Satisfiability I: Previous: Summary
Matt Ginsberg 2004-02-19