  The DIMACS 32-bit parity problem is a satisfiability (SAT) problem hard to
solve. So far, EqSatz by Li is the only solver which can solve this problem.
However, This solver is very slow. It is reported that it spent 11855 seconds
to solve a par32-5 instance on a Maxintosh G3 300 MHz. The paper introduces a
new solver, XORSAT, which splits the original problem into two parts:
structured part and random part, and then solves separately them with WalkSAT
and an XOR equation solver. Based our empirical observation, XORSAT is
surprisingly fast, which is approximately 1000 times faster than EqSatz. For a
par32-5 instance, XORSAT took 2.9 seconds, while EqSatz took 2844 seconds on
Intel Pentium IV 2.66GHz CPU. We believe that this method significantly
different from traditional methods is also useful beyond this domain.
