Learning and Relevance Bounds

The idea of relevance also has a natural generalization to the pseudo-Boolean setting. Recall the basic definition from Section 2.2:

Definition 3.15   Let $c$ be a clause and $P$ a partial assignment. Then $c$ is $i$-irrelevant if the number of literals in $c$ that are either unvalued or true under $P$ is at least $i+1$.

Proposition 3.16   Given a partial assignment $P$ and a Boolean clause $c$, $c$ is $i$-irrelevant if and only if $\mbox{\tt poss}(c,P) \geq i$.

Proof. In the Boolean case, the number of literals in $c$ that are either unvalued or true is $\mbox{\tt poss}(c,P)+1$ since the right hand side of the constraint is always 1. So the irrelevance condition is

$$\mbox{\tt poss}(c,P)+1 \geq i+1$$

and the result follows.         $\mathchoice{\vcenter{\hrule height.4pt \hbox{\vrule width.4pt height3pt \kern ... ...vrule width.3pt height1.5pt \kern 1.5pt \vrule width.3pt} \hrule height.3pt}}$

In the pseudo-Boolean case, additional learning techniques are also possible. Before we present these ideas in detail, however, let us point out that some sort of inferential extension is needed if we are to overcome the shortcomings of DPLL as revealed by the pigeonhole and other problems. After all, recall Proposition 3.14: pseudo-Boolean inference generalizes Boolean resolution. So if we begin with a Boolean axiomatization (as we did in the pigeonhole problem), any derivation using our techniques will be reproducible using conventional resolution-based methods, and will therefore be of exponential length. (A majority of the inference steps in the various proofs of Proposition 3.2 are not resolution steps in that no literal cancellations occur.)