over basic events. The proof follows similar lines to the proof of NP-hardness of 2PSAT

to probabilistic query over basic events that is directed to probabilistic knowledge base

given by Georgakopoulos et al. (1988).

Let V ; E be nite undirected graph. We construct probabilistic knowledge base
B; KB as follows. We initialize B; KB with fBg; ). For each node V we increase
B by the new basic events Bv Bv and Bv For each node V and for each i f ; ; g
we increase KB by B Biv )[1; 1] and Biv B)[1 ; 3]. For each node V and for each
i; j f ; ; g with i we increase KB by Bj
v Biv )[0; 0]. For each edge fu; vg E and for
each i f ; ; g we increase KB by Biv Biu)[0; 0]. It is easy to see that the probabilistic
knowledge base B; KB can be constructed in polynomial time in the size of V ; E).
Now, we show that V ; E is 3-colorable i f ; g is the tight answer to the
probabilistic query B B)[ ; x to B; KB), or equivalently, i KB is satisable:
If V ; E is 3-colorable, then there exists mapping c from V to f ; ; g with c u
c for all edges fu; vg E Thus, if  is cyclic permutation of the members in f ; ; g
and if c ; c V f ; ; g are dened by c  c )) and c  c )) for all
nodes V then also c u c and c u c for all edges fu; vg E For
f ; ; g let Aj B such that Aj B and Aj Biv i cj i for all nodes V
and i f ; ; g If Pr B [0; 1] is dened by Pr A for all A fA ; A ; A g and
by Pr A for all A B fA ; A ; A g then Pr is model of KB
Conversely, if there is model Pr of KB then there is an atomic event A B with
Pr A 0. Thus, if c V f ; ; g is dened by c i i A Biv for all nodes V
then c u c for all edges fu; vg E Hence, V ; E is 3-colorable. 2
Hence, it is unlikely that there is an ecient algorithm for computing the tight answer

to all probabilistic queries over basic events that are directed to any given probabilistic

knowledge base over basic events. However, there may still be ecient algorithms for

solving more specialized probabilistic deduction problems.

The rest of this work deals with probabilistic deduction in conditional constraint trees.

The next section provides motivating example, which gives evidence of the practical

importance of this kind of probabilistic deduction problems.

informed lies between 0.60 and 0.70, that the probability of student being well-informed

given she is successful is greater than 0.85, that the probability of student being successful

given she is well-prepared is greater than 0.95, and that the probability of student being

well-prepared given she is successful is greater than 0.95.

This probabilistic knowledge completed by further probabilistic estimations is given by

## 2.3 Motivating Example

senior student in mathematics describes her experience about being successful at the uni- uenced by how well-informed wi and how well-prepared wp the student is. Well-informedness can be reached by interviewing uenced by how It is estimated that the probability of student being successful given she is well-
$${\mathsf{w p}}$$
versity as follows. The success of student su is in

professors pr or by asking senior students st). Being well-prepared is in

much time is invested in books bo), exercises ex), and hobbies ho).
