Computer Science – Data Structures and Algorithms
Scientific paper
2007-03-02
Computer Science
Data Structures and Algorithms
Scientific paper
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.
No associations
LandOfFree
XORSAT: An Efficient Algorithm for the DIMACS 32-bit Parity Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with XORSAT: An Efficient Algorithm for the DIMACS 32-bit Parity Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and XORSAT: An Efficient Algorithm for the DIMACS 32-bit Parity Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-284476