Parity Problem

Next: A Synthetic Benchmark Up: Some SAT Benchmarks Visualised Previous: Pigeon Hole Problem

Parity Problem

Learning parity, from the DIMACS SAT Competition benchmark suite, problem par16-2.cnf. The parity problems have a clear sub-structure that looks tightly coupled and highly constrained. Identifying and solving structures such as these may be critical to solving the entire problem.

**Figure 10:** Parity Problem, Cooccurrence of Variables
$\begin{figure}\epsfig{figure=images/par16-2_vco,width=\textwidth} \end{figure}$

**Figure 11:** Parity Problem, Cooccurrence of Literals
$\begin{figure}\epsfig{figure=images/par16-2_lco,width=\textwidth} \end{figure}$

**Figure 12:** Parity Problem, Basic Implicative Interpretation
$\begin{figure}\epsfig{figure=images/par16-2_imp,width=\textwidth} \end{figure}$

Last modified: 2004-03-17
Andrew Slater