** Next:** Strengthening
** Up:** Pseudo-Boolean and Cardinality Constraints
** Previous:** Inference and Resolution

##

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

be a clause and

a partial assignment.
Then

is

*-irrelevant* if the number of literals in

that are either unvalued or true under

is at least

.

**Proposition 3.16**
Given a partial assignment

and a Boolean clause

,

is

-irrelevant if and only if

.

**Proof.** In the Boolean case, the number of literals in that are
either unvalued or true is
since the right hand side of
the constraint is always 1. So the irrelevance condition is

and the result follows.

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.)

**Subsections**

** Next:** Strengthening
** Up:** Pseudo-Boolean and Cardinality Constraints
** Previous:** Inference and Resolution
Matt Ginsberg
2004-02-19