The Minimal Disagreement Parity Problem as a Hard Satisfiability Problem
One common approach to generating hard instances for SAT algorithms is to encode other NP-complete problems into SAT. An obvious problem with this approach is that many NP-complete problems are trivially solvable in the average case [4]. One solution to this problem is to choose problem classes which are randomly self-reducible. As we show in section 3, randomly self-reducible problems are as hard in the average case as they are in the worst case. The minimal disagreement parity (MPD) problem is a simple example of a randomly self-reducible problem. Informally the problem is the following: given a set of sample input vectors and a set of sample parities, find the bits of the input vectors on which the parities were computed. In the absence of noise this problem has a known polynomial solution. In the presence of a moderate amount of noise (i.e., corruption of around 1/4 of the parity bits), however, there is reason to believe that the problem is quite hard.