The Inferential Complexity of Bayesian and Credal Networks

1 Introduction

This paper builds a picture of inferential complexity in graphtheoretical models of uncertainty that goes signi�cantly beyond existing results. We focus on Bayesian and credal networks � the former is a purely probabilistic model, while the latter admits interval and set valued probabilities and generalizes several theories of uncertainty. There already is quite a solid understanding about the inferential complexity of Bayesian networks; we add to this picture a new class of networks that strengthens existing results, and a new type of problem, maximin a posteriori (MmAP), that can be of interest in game-theoretic settings. Our main contributions are related to credal networks, as little is known at this point concerning their inferential complexity: we present new results concerning computation of probability bounds, most probable explanations (MPE) and maximum a posteriori (MAP). We show that, rather surprisingly, the MPE problem without observations in credal networks of bounded width is polynomial, while the MPE problem with observations and the MAP problem are Σp2 -complete for credal networks.

We also strengthen the connection between Bayesian and credal networks by showing links between the computation of probability bounds, the MAP and the MmAP problems. Our results suggest that moving from point to interval/set valued probabilities takes us �one step up� in terms of complexity classes.

Fabio Gagliardi Cozman1

Section 2 presents a few de�nitions and, most importantly, tries to justify our interest in credal networks. Section 3 describes the problems we are interested in. Section 4 contains our new results; in particular, Table 1 offers a summary of our contributions. Section 5 concludes the paper and suggests future research.

2 Bayesian and Credal Networks

A Bayesian network (or BN) represents a single joint probability density over a collection of random variables. We assume throughout that variables are categorical; variables are uppercase and their assignments are lowercase.

De�nition A Bayesian network is a pair (G, P), where: G = (VG, EG) is a directed acyclic graph, with VG a collection of vertices associated to random variables X (a node per variable), and EG a collection of arcs; P is a collection of conditional probability densities p(Xi|pa(Xi)) where pa(Xi) denotes the parents of Xi in the graph (pa(Xi) may be empty), respecting the relations of EG.

In a BN every variable is independent of its nondescendants nonparents given its parents (Markov condition). This structure induces a joint probability density by the expression p(X1, . . . , Xn) = ∏i p(Xi|pa(Xi)). Given a BN, E denotes the set of observed variables in the network (the evidence); e denotes the observed value of E.

We consider the class of networks with bounded induced-width (or BIW); that is, networks where the subjacent graph (obtained removing arc's directions) of G has maximum degree and induced-width bounded by log(f(s)). We de�ne f(s) as a polynomial function in the size s of input (this size is evaluated over all information needed to specify the problem). We also consider the class of polytrees (or PT); that is, a BIW network where the subjacent graph of G has no cycles. Otherwise, a network is said multiply-connected. Note that our de�nition of BIW networks is not, as usually done, based on �xed inducedwidth; rather, we allow the induced-width to vary with the network size.

Credal networks generalize Bayesian networks by allowing each variable to be associated with sets of joint probability measures rather than single probability measures [Cano et al., 1993; Cozman, 2000a]. Such graph-theoretical models can be viewed as Bayesian networks with relaxed numerical parameters; they can be used to study robustness of probabilistic models, to investigate the behavior of groups of experts, or to represent incomplete or vague knowledge about probabilities. Sets of probability measures are suf�ciently powerful to represent belief functions, possibility measures, qualitative probabilities, and probabilistic logic statements, thus offering a general language that can convey many models of interest in arti�cial intelligence [Walley, 1996].

A set of probability distributions is called a credal set [Levi, 1980]. A credal set for X is denoted by K(X). A conditional credal set is a set of conditional distributions, obtained applying Bayes rule to each distribution in a credal set of joint distributions [Walley, 1991]. Given a credal set K(X), the lower probability and the upper probability of event A are de�ned respectively as P(A) = minp(X)∈K(X) P(A) and P(A) = maxp(X)∈K(X) P(A). We assume that, given a credal set, �nding a lower/upper probability is a polynomial operation.

De�nition A credal network is a pair (G,K), where: G = (VG, EG) is a directed acyclic graph, with VG a collection of vertices associated to random variables X (a node per variable), and EG a collection of arcs; K is a collection of conditional credal sets K(Xi|pa(Xi)), respecting the relations implied by EG.

We assume a Markov condition in credal networks: every variable is independent of its nondescendants nonparents given its parents. In this paper we adopt the concept of strong independence; that is, the joint credal set represented by a credal network is a set where each vertex factorizes as a Bayesian network [Cozman, 2000b]. Thus we can really view a credal network as a set of Bayesian networks, all with identical graphs. Credal networks can also be classi�ed as polytree, bounded induced-width or multiply-connected.

3 Reasoning

In this section we present decision versions of the inferences we focus in this paper.

De�nition BN-Pr: given a Bayesian network (G, P), evidence E = e with E ⊆ X, a query variable Q ∈ X \ E and its category q, and a rational number r, is P(q|e) > r?

Note the following distinction between MPE problems with or without evidence; the reason for this will be indicated later:

De�nition BN-MPE: given a Bayesian network (G, P), evidence E = e with E ⊆ X and a rational number r, is there an instantiation x for X \ E such that P (x, e) > r?

De�nition BN-MPEe: given a Bayesian network (G, P), evidence E = e with E ⊆ X and a rational number r, is there an instantiation x for X \ E such that P (x|e) > r?

De�nition BN-MAP: given a Bayesian network (G, P), evidence E = e with E ⊆ X, a set Q ⊆ X \ E and a rational number r, is there an instantiation q for Q such that P (q|e) > r?

We introduce the maximin a posteriori problem, which may be of interest in applications involving game-theoretic behavior with maximizers and minimizers [Kakade et al., 2001]:

De�nition BN-MmAP: given a Bayesian network (G, P), some evidence E = e with E ⊆ X, the sets A ⊆ X \ E and B ⊆ X \ E, with A ∩ B = ∅ and a rational number r, is there an instantiation a for the A variables such that minb P (a, b|e) > r?

The corresponding problems in CN are now de�ned.

De�nition CN-Pr: given a credal network (G,K), evidence E = e with E ⊆ X, a query variable Q ∈ X \ E and its category q and a rational number r, is P(q|e) > r?

In this de�nition we use upper queries, but lower queries may be of interest too. We can show that both queries lead to identical complexity results:

Lemma 1 Evaluating marginal lower probabilities in CN is as hard as evaluating marginal upper probabilities.

Proof Suppose we have a CN-Pr with marginal query Q = q. The calculation of P (q|e) can be done by inserting a binary child Q′ to Q, where P(q′ |Q) = 1 if Q ̸= q and 0 otherwise. Now P (q′ |e) = max ∑Q̸=q P (Q|e) = 1 - P (q|e). □

We now de�ne maximin versions of MPE and MAP in credal networks (we could alternatively de�ne maximax versions for these problems, with possibly different complexities).

De�nition CN-MAP: given a credal network (G,K), some evidence E = e with E ⊆ X, a set Q ⊆ X \ E and a rational number r, is there an instantiation q for the Q variables such that P (q|e) > r?

CN-MPEe is obtained when CN-MAP has Q = X \ E. CN-MPE is CN-MPEe without evidence, that is, Q = X. We use abbreviations to refer to these problems (e.g. PT-CN-Pr is the belief updating problem in a polytree credal network).

4 Complexity results

Table 1 summarizes relevant complexity results. 1 We start by explaining the origin of the results in this table (numbering matches the numbers in the table):

1. [Dechter, 1996] describes algorithms with exponential time complexity on the induced-width of an elimination order; [Eyal, 2001] shows how to obtain a constantfactor approximation to optimal order in polynomial time for networks with bounded degree and bounded induced-width by log(f(s)). Note that the result here is sightly different from the one in [Dechter, 1996]; we refer to the actual induced width of the graph, not the induced width of an ordering.
2. [Roth, 1996] shows complexity of functional version, [Litmman et al., 2001] takes the decision version.
3. [Shimony, 1994] shows (by reduction from the vertex cover problem) that BN-MPE is NP-Complete, while Theorem 2 shows that BN-MPEe is PP-Complete.

1 We assume that the reader is familiar with notions of complexity theory; for an introduction see [Papadimitriou, 1994]. Polynomial time means polynomial time in the size of input. A reduction means a polynomial time reduction; when a problem is solvable by another, there is a reduction from the former to the latter.

1. [Park, 2002] reduces MAXSAT problem to BN-MAP in polytrees, a result that can be extended to BIW networks as both problems belong to NP (given the polynomial nature of BN-Pr in BIW networks).
2. [Park and Darwiche, 2004] by reduction from E-MAJSAT.
3. Theorem 8.
4. The complexity of BN-MAP implies it.
5. Theorem 3.
6. [Cozman et al., 2004] by a reduction from E-MAJSAT.
7. Theorem 5.
8. Theorem 6.
9. Theorem 7.
10. BN-MPE and PT-CN-MPEe ensure it.

In the context of Bayesian networks, the difference between MPE and MPEe may seem academic, because any most probable explanation can be found with BN-MPE. However the same is not true for credal networks, where one cannot �nd a most probable explanation with evidence by simply running a version of MPE � and note that CN-MPE and CN-MPEe do display non-trivial differences. In fact, these differences were our motivation for differentiating MPE from MPEe. The following theorem clari�es the difference between these problems for Bayesian networks.

Theorem 2 BN-MPEe is PP-Complete.

Proof Pertinence is obtained from the fact that, after making a PP query to �nd P (e) (this query is made once), we can decide whether a given instantiation x has P(x|e) > r in linear time, by multiplying the probabilities. To show hardness, we reduce the decision problem #3SAT(≥ 2n/2) to it, which is PP-Complete [Bailey et al., 2001] and can be stated as: Given a set of boolean variables X = {X1, . . . ,Xn} and a 3CNF formula φ(X) with clauses {C1, . . . , Cm}, is φ(X) satis�ed by at least 2n/2 of the instantiations of X?

We construct a BN with binary nodes X1, . . . ,Xn (xi and xi are the categories) and C1, . . . ,Cm (ci and ci), where Xi has no parents and uniform prior and Ci has three parents (the variables contained in the clause) with probabilities respecting the truth table for the clause. Furthermore, we insert a dummy binary node Y appearing non-negated in every clause

(there will be 2n instantiations with {Y = y} satisfying φ; this ensures that the formula is satis�able). Now we solve the BN-MPEe problem with queries X1, . . . , Xn, Y and evidence Ci = ci for all 1 ≤ i ≤ m (indicating that all Ci are true). Then P(X, Y |c1, . . . , cm) is equal to

where #sats is the total number of satisfying instantiations. So, maxP(X, Y |c1, . . . , cm) ≤ 1 2n+2n/2 implies that formula φ(X) is satis�ed by at least 2n/2 of all X instantiations. Note that if maxP(X, Y |c1, . . . , cm) = α and α > 1 2n+2n/2 , then P(X, Y |c1, . . . , cm) = α for all satisfying instantiations, which implies that there are less than 2n/2 instantiations of X satisfying φ(X). □

The hardness of PT-CN-Pr was stated by [da Rocha and Cozman, 2002], but the proof there was �awed, and the central argument used zero probabilities and vertex-based description in an essential way. The following proof corrects these dif�culties.

Theorem 3 PT-CN-Pr and BIW-CN-Pr are NPComplete.

Proof Pertinence of BIW-CN-Pr (which ensures pertinence of PT-CN-Pr) is immediate, as choosing a vertex of each credal set we have a BIW-BN-Pr problem to solve, which is polynomial. To show hardness we reduce the MAX-3-SAT problem to PT-CN-Pr. It can be formulated as follows: Given a set of boolean variables {X1, . . . , Xn}, a 3CNF formula with clauses {C1, . . . , Cm} and an integer 0 ≤ k ≤ m, is there an assignment for the variables that satis�es at least k clauses? Initially we remove all clauses that have both xi and xi and decrement k for each elimination (because those clauses are already satis�ed). For each variable Xi we construct two nodes, namely Xi and Si. The former is binary, has no parents and represents the state of Xi; the probabilities P(Xi = xi) and P(Xi = xi) are in [ε, 1-ε] (0 < ε < 1 m+1 is a small constant). The latter may assume m+ 1 categories

(from 0 to m), has Si-1 and Xi as parents and is de�ned by

P(Si = c|Si-1 = c, xi) = 0 if xi ∈ Cc, or 1 otherwise P(Si = c|Si-1 = c, xi) = 0 if xi ∈ Cc, or 1 otherwise P(Si = c|Si-1 ̸= c,Xi) = 0 for Xi ∈ {xi, xi},

for c ̸= 0. When Si = 0, we have:

The rules above guarantee coherency in probabilities; note that we include a dummy node S0 with P(S0 = c) = 1 m+1 for all c. Now, consider P(Sn = c) for c ̸= 0. Note that P(Sn = c) = P(S0 = c) ∏i P(Si = c|Si-1 = c) because, for c ̸= 0, every time {Si = c} and {Si-1 ̸= c} appear together we are led to zero. Let Ac,i be de�ned as follows:

We get P(Sn = c) = 1 m+1 ∏i∈{1,...,n} Ac,i. Note that Ac,i may assume three values: Ac,i = 1 if Xi does not in�uence Cc; Ac,i = ε if Xi satis�es Cc and Ac,i = 1 - ε if Xi does not satisfy Cc. We may conclude that if P(Sn = c) ≤ α = (1 - ε)2 ε, then some Xi satis�ed Cc. Furthermore, we know that if Cc was not satis�ed, then P(Sn = c) = β = (1 - ε)3 . Note that α < β. To �nd out how many clauses were not satis�ed, we have to sum over all categories of Sn, obtaining P (Sn = 0) = 1 - ∑c∈{1,...,m} P (Sn = c) and thus

P(Sn = 0) minimizes this sum. We de�ne

and then calculate r0, r1, . . . until rh ≤ α or h = m - 1. We know that 1 - P(Sn = 0) is the minimum sum of all P(Sn = c), for c ̸= 0. This sum is composed by two types of terms: those which are equal to β and those which are less than or equal to α. So what we are verifying with rh is whether there are more than h terms of the sum that are equal to β or not. The last thing should be noted is that ε < 1 m+1 ensures that if just one term of the sum equals to β, then the sum is greater than mα, that is, if the sum is composed by m - 1 terms equal to ε3 and just one equal to β, it must sum greater than mα, because one clause was not satis�ed. ε < 1 m+1 ensures that everywhere it is necessary (for any h). Thus the inference P(Sn = 0) solves MAX-3-SAT problem. If rh > α for all 0 ≤ h ≤ m-1, then no clause was satis�ed. Otherwise h counts how many clauses were not satis�ed. □

Because of the reduction from MAX-3-SAT, we can state that there is no polynomial time approximation scheme for PT-CN-Pr (or BIW-CN-Pr) unless P=NP.

Remark The proof still holds if we substitute all ε by zero; the proof becomes simpler but depends on events of zero probability, which may be inconvenient, as pointed out by [Zaffalon, 2003]. Note also that the proof can be rewritten using inequalities instead of vertices, because all credal sets are in binary nodes (pertinence and hardness still hold).

It is known that CN-Pr is solvable by BN-MAP, by conducting a CCM transform in a credal network [Cozman, 2000a]. The following lemma presents the reverse connection between inferences in Bayesian and credal networks.

Lemma 4 BN-MAP is solvable by CN-Pr with joint queries without changing the topology of the network among the three types de�ned.

Proof Suppose X1, . . . ,Xn are the MAP variables. Add a binary child X ′ i to each Xi with P(X′ i |Xi) ∈ [0, 1] and the constraint ∑Xi P (x′i |Xi) = 1. Now we have

After evaluating P(x′1 , . . . , x′n |e), we just have to look at each X′ i node and set Xi according to which of the P(x′i |Xi) is equal to one (exactly one will be). □

It should be noted that joint queries are not more dif�cult than single marginal queries: we have that CN-Pr with joint queries is still NP PP -Complete and BIW-CN-Pr with joint queries is still NP-Complete.

Theorem 5 PT-CN-MPE and BIW-CN-MPE are solvable in polynomial time.

Proof It is enough to realize that the inner min of the BIW-CN-MPE query maxx minP ∈K(X) ∏i P (xi|pa(xi)) factorizes, as the network is locally speci�ed (note that xi's are consistent with the observation e). The optimization becomes maxx ∏i P(xi|pa(xi)), which is equivalent to BIW-BN-MPE. □

Theorem 6 CN-MPE is NP-Complete.

Proof Hardness is immediate, because BN-MPE is NPComplete and can be trivially transformed to a CN-MPE (we just have to use credal networks composed by single probability densities). Pertinence is reached because, given an assignment x to the variables, the value of P(x) is given by ∏i P(xi|pa(xi)). This holds because each credal set K(xi|pa(xi)) is locally speci�ed. □

Theorem 7 PT-CN-MPEe, BIW-CN-MPEe, PT-CN-MAP and BIW-CN-MAP are all ΣP2 -Complete.

Proof Pertinence of them is immediate as BIW-CN-MAP belongs to ΣP2 (given the MAP variables, we get a BIW-CN-Pr to solve). To see hardness we reduce to PT-CN-MPEe a version of QSAT2 that is ΣP2 -Complete: Given a set of variables X1, . . . ,Xn, an integer 0 < k ≤ n and a boolean 3CNF formula φ(X) over these variables, is it true that, for all instantiations to the �rst k variables, there is an instantiation of the remaining n - k that satis�es φ(X)?

Initially we construct a network similar to that of Theorem 3. The variables X1, . . . ,Xk are de�ned the same way as there. The variables Xk+1, . . . ,Xn become ternary, assuming the categories xi, xi, oi. Their probabilities are: P(Xi = oi) = ε and P(Xi = xi), P(Xi = xi) belong to [0, 1 - ε], where 0 < ε < 1 m+2 is a small constant. The probabilities of Si given its parents are the same as there, except when i > k. In these cases we have P(Si = c|Si-1 = c, oi) = 0, for c ̸= 0 (the case when c = 0 remains the same, that is, equals to 1).

Furthermore, we add a dummy node Q with Sn as parent and P(q|Sn = c) = 0 for c ̸= 0 and 1 otherwise. We will solve the PT-CN-MPEe problem max P (X, S|q), where S = {S0, . . . , Sn} and X = {X1, . . . ,Xn}. Let X- be {X1, . . . ,Xk} and X+ be {Xk+1, . . . ,Xn}; then

First note that the given q forces Sn = 0 to get a nonzero probability. Furthermore, for all instantiations x-, x+, s of the variables, there is another instantiation with s′ = {∀iSi = 0} that has its probability greater than the former, that is, P(x-, x+, s′ |q) > P(x-, x+, s|q). This holds because the Si nodes are not credal and the conditional probabilities P(Si = 0|Si-1 = 0) are equal to 1, for all i. Thus we know that the solution of the MPEe problem will be attained in an instantiation where all Si are set to 0. Besides that, we have that choosing the category oi for all X+ variables lead us to greater probabilities than if we choose any other. That is,

where o denotes {Xi = oi for i ∈ {k + 1, . . . , n}} and s denotes {∀i Si = 0}. If we choose a category different from oi whenever possible, the maximum probability would not reach the same value (in fact it will be zero, because P(Xi ̸= oi) ∈ [0, 1-ε], and thus it may assume value zero).

When �nding P(X -, o, s|q), the numerator P(X -) will become εk , because any solution that does not make P(X -) = εk will not be a minimum for P(X -, o, s|q) (remember that ε < 1 m+2 ). This holds because just one X - variable using the extreme point (1 - ε) instead of ε is enough to make P(X-, o, s|q) too large:

where R and R′ are any possible values for the sum ∑c̸=0 P(Sn = c) that appears in the denominator (note that these sums are restricted in [0, m m+1 ] by the probabilities of the network).

Summarizing, all S variables in the solution of MPEe are set to zero, all X + variables are set to o, and the instantiation chosen for X - makes P(X-) = εk , which implies that if xi belongs to the instantiation of X -, then P(xi) = ε and P(xi) = 1 - ε (the opposite case is analogous). This means that the vertices of the credal sets of the X - nodes are completely �xed by the instantiation chosen. Thus the only credal sets that can �oat in the denominator are the X + variables (Si variables are not credal and X - are already �xed as indicated). So, processing the MPEe we have

where min ∑c̸=0 P(Sn = c) is evaluated over all possible vertices of the X + credal sets (we know that P(Xi = oi) is set to ε, but the probabilities P(Xi = xi) and P(Xi = xi) may vary between 0 and 1 - ε).

The formula φ(X) will be satis�ed by X - and X+ if the sum ∑c̸=0 P(Sn = c) is less than δ1 = m m+1 (1 - ε)2 ε(1 - ε)n-k (this is the maximum value that a satis�ed φ(X) may assume). All unsatis�ed formulas lead to greater values. In fact the smallest value that a unsatis�ed formula implies in the sum is greater than δ2 = m m+1 (1 - ε)n-k+3 . Note that δ2 > δ1.

If we query the PT-CN-MPEe problem maxP(X, S|q) with r = 1 m+1 εn 1-δ1 and get a negative answer, then for all instantiations to X -, there is an instantiation to X + that satisfy φ(X) (that is, the sum is bounded by δ1). If the answer is positive, then there does exist an instantiation to X - where no instantiation to X + can make φ(X) satis�ed. □

Theorem 8 PT-BN-MmAP and BIW-BN-MmAP are ΣP2 - Complete.

Proof Pertinence of BIW-BN-MmAP (which ensures pertinence of PT-BN-MmAP) is trivial. Given a instantiation for the MAP variables, we need to solve a minimization over the Y variables, which is NP-Complete (see it as a BIW-CN-Pr using Lemma 4). Hardness of PT-BN-MmAP (which ensures hardness of BIW-BN-MmAP) is reached by a reduction from another version of QSAT2 that is ΣP2 -Complete: Given a set of variables X1, . . . ,Xn, an integer 0 < k ≤ n and a boolean 3DNF formula φ(X) over these variables, is there an instantiation to the �rst k variables such that, for all instantiations of the remaining n-k, φ(X) is satis�ed?

We construct again a network following the ideas of Theorem 3. It includes a binary node to each Xi, without parents and with uniform prior. There are n nodes Si with parents Si-1 and Xi. They have m+ 1 categories and are de�ned as follows (for c ∈ {1, . . . ,m} and i ∈ {1, . . . , n}):

The conditional probabilities of Si given xi are de�ned analogously. The probabilities of P (Si = 0|Si-1, Xi) ensure that they sum exactly 1, as done in Theorem 3. Furthermore, P(S0) has uniform prior and we insert an additional binary node Q with Sn as parent, having P(q|Sn = c) = 1 if c ̸= 0 and 0 otherwise.

So, we have that P(X|q) = 1 2n P(q|X) P(q) is equal to

where Ac,i = ∑Xi P(Si = c|Si-1 = c,Xi)P(Xi) for i ∈ {1, . . . , n}. Ac,i assumes value zero only when the variable it represents denies the clause c. The numerator of P(X|q) sums how many clauses are satis�ed by the instantiation of X variables. Let X - = {X1, . . . ,Xk} and X+ = {Xk+1, . . . ,Xn}. We have minX+ P(X-,X+|q) = 0 if, given the instantiation for the X - variables, there is an assignment to X + variables that can deny φ(X). This way, questioning if PT-BN-MmAP problem with MAP variables X- and evidence q (which maximizes minX+ P(X|q)) has non-zero answer is enough to solve the QSAT2 problem. Given this X - instantiation, all X + will satisfy φ(X). □

5 Conclusion

We can summarize the contributions of this paper as follows. Concerning Bayesian networks, we have �rst introduced a more general de�nition of bounded induced-width networks (demonstrating that many problems where inducedwidth actually grows with the network remain polynomial), and we have shown the difference between the BN-MPE and the BN-MPEe problems. More importantly, we have introduced the MmAP problem and presented its complexity. A possible improvement of our results would be to present a completeness result for multiply-connected networks.

Our most signi�cant results pertain to credal networks, with direct implications to models that handle interval and set probabilities, belief functions, possibility measures, qualitative probabilities, and families of probabilistic logic. We have clari�ed the so far unexplored complexity of CN-MPE, CN-MPEe, and CN-MAP. The polynomial character of CN-MPE in some cases is rather surprising.

There are several interesting problems still to be explored. For example, binary networks (Bayesian and credal) could display lower complexity than their non-binary counterparts in problems such as PT-BN-MAP, BIW-BN-MAP and BIW-CN-Pr. These problems belong to NP and are clearly related, but are there polynomial time algorithms to solve them? We conjecture there are not, even as we note that there is a polynomial algorithm to solve CN-Pr in binary polytrees [Fagiuoli and Zaffalon, 1998].

Acknowledgments

We thank Aritanan Gruber for indicating relevant complexity results, Carlos Guestrin for pointing out a �aw in [da Rocha and Cozman, 2002], Thomas Lukasiewicz for initial thoughts on the complexity of credal networks, and a reviewer for suggesting a short proof for Theorem 5. This research received support from HP Brazil R&D; the second author was partially supported by CNPq, Brazil.