A Constraint Network Under Conditional Uncertainty (CNCU) is a formalism able to model a constraint satisfaction problem (CSP) where variables and constraints are labeled by a conjunction of Boolean variables, or booleans, whose truth value assignments are out of control and only discovered upon the execution of their related observation points (special kind of variables). At the start of the execution of the CNCU (i.e., the online assignment of values to variables), we do not know yet which constraints and variables will be taken into consideration nor in which order. Weak controllability implies the existence of a strategy to execute a CNCU whenever the whole uncontrollable part is known before executing. Strong controllability is the opposite case and implies the existence of a strategy to execute a CNCU always the same way no matter how the uncontrollable part will behave. Dynamic controllability implies the existence of an adaptive strategy to execute the CNCU taking into account how the uncontrollable part is behaving. In this paper we classify the computational complexity of weak, strong and dynamic controllability of CNCUs. We prove that weak controllability is Π2p-complete, strong controllability is NP-complete and dynamic controllability is PSPACE-complete.
{v1, v2, v3}
X1 {v1, v2, v3}
X2 • X , V, D are the same as those given for CNs in Definition 1. • O ⊆ X = {A?, B?, . . . } is a set of observation points. • B = {a, b, . . . , z} is a finite set of booleans. O : B → O is a bijection assigning a unique observation point A? to each boolean a. When A? is assigned a value v ∈ D(A?), the truth value of a is set by Nature and no longer changes. • L : X → B∗ is a mapping assigning a label ` to each variable X. • ≺ is a partial order on X . We write X1 ≺ X2 to express that X1 must be executed before X2. • C is a finite set of conditional constraints of the form ` ⇒ RS , where ` ∈ B∗ and RS is a classic relational constraint.
Definition 3. A CNCU is well defined iff all labels are consistent and: 1. For each X ∈ X , if a literal a (or ¬a) ∈ L(X), then L(O(a)) ⊆ L(X) and O(a) ≺ X. 2. For each constraint (RS , `) ∈ C, VX∈S L(X) ⊆ ` and if a literal a (or ¬a) ∈ L(X), then L(O(a)) ⊆ `. 3. L(X1) ∧ L(X2) is consistent whenever X1 ≺ X2.
Regarding the notions of well-definedness (initially proposed for conditional temporal networks in [
Definition 4. A CNCU N is weakly controllable if every projection P of N satisfies two properties: (1) there exists a total extension ≺T of ≺, and (2) P is a consistent CN.
Fig. 1b is weakly controllable. If s(e) = > (Fig. 1c), then E? = v1, X1 = v1, X2 = v2 and X3 = v2 (in this order). If s(e) = ⊥ (Fig. 1d), then E? = v1, X1 = v2 and X2 = v2 (again, in this order). Definition 5. A CNCU N is strongly controllable if there exists a total extension ≺T of ≺ and an assignment α of values to the variables such that α satisfies all constraints in each scenario.
An initial approach to strong controllability is that of computing a super-projection obtained by wiping
out labels on variables and constraints [
For weak and strong controllability we just make sure that a total order for X exists (that’s why we grayed it in Fig. 1c, Fig. 1d and Fig. 1e). Instead, dynamic controllability of CNCUs is a matter of order. Definition 6. A CNCU is dynamically controllable if there exists a dynamic strategy operating in real time that guarantees that we end up with all constraints in C evaluating to true. A strategy is called dynamic if the variable executed next and the value assigned to it only depend on the partial scenario revealed up to that point.
Note that despite variables specify labels, assigning values to those that have become irrelevant is superfluous but not wrong (we can always ignore those assignments at the end of the execution). Fig. 1b is uncontrollable if X1 is executed before E?. Indeed, if X1 = v1 and E? = v1 and then s(e) = ⊥ (or X1 = v2 and E? = v2 and then s(e) = >), there is not valid value for X2 satisfying (=, ¬e) or (6=, e), respectively. Instead, the CNCU is dynamically controllable if E? is executed first. A possible execution strategy is: E? = v1 (always). If s(e) = >, then X1 = v1, X2 = v2 and X3 = v2, whereas if s(e) = ⊥ then X1 = v2 and X2 = v2 (we omit irrelevant variables). 2
Complexity of Weak, Strong and Dynamic Controllability Let α : X → V be an assignment of values to the variables. Given a CNCU N = hX , V, D, O, B, O, L, ≺, Ci and a pair (s, α), where s is a scenario and α an assignment, we say that (s, α) |= N iff (1) for each X ∈ X , α(X) ∈ D(X) and (2) for each ` ⇒ R{Xi1 ,...,Xin } ∈ C, if s |= `, then (α(Xi1 ), . . . , α(Xin )) ∈ R{Xi1 ,...,Xin }. Theorem 1. Strong controllability of CNCUs is NP-complete.
Proof. Hardness: Consequence of the fact that deciding consistency of CNs is NP-hard and it is a special case of deciding strong controllability of CNCUs (when the set of observations is empty). Membership: ({(1)}, y1) ({(0)}, ¬y1)
({(1)}, y2) ({(0)}, ¬y2) as a certificate of YES consider a pair comprising a total extension ≺T of ≺ and a total assignment α to the variables that obeys all constraints regardless of the truth assignment s to the booleans. Notice that any single constraint ` ⇒ R is satisfied by α for each possible s if and only if α satisfies R, and since we have a finite number of constraints to check, the overall check is polynomial.
To prove that deciding weak controllability of CNCUs is Π2p-hard and deciding dynamic controllability of CNCUs is PSPACE-hard, we first describe a polynomial time algorithm that, given in input any quantified boolean formula (QBF) Φ with n variables and m clauses, and at most 3 literals in each clause constructs a CNCU NΦ with at most 2 × n variables with binary domain, exactly n booleans, and at most (2 × n) + m constraints each one of arity of at most 3. With this, the description length of NΦ is at most polynomial in m and n. The Π2p-hardness and PSPACE-hardness results are then obtained in Lemma 1 and Lemma 2 where it is shown that particular instances of Φ are satisfiable iff NΦ is weakly controllable and dynamically controllable, respectively. Fig. 2 provides an example of use of QBF2CNCU (Algorithm 1).
Algorithm 1: QBF2CNCU(Φ)
Input: A a quantified boolean formula Φ ≡ Q1x1, . . . , Qnxnϕ where Qi ∈ {∃, ∀} (1 ≤ i ≤ n) and ϕ ≡ C1 ∧ · · · ∧ Cm is a 3-CNF specifying m clauses over the variables x1, . . . , xn
Output: A CNCU NΦ = hX , V, D, O, B, O, L, ≺, Ci. 1 For each “∃x” in Φ, we add a variable X to X such that D(X) = {0, 1} and L(X) = . 2 For each “∀y” in Φ we add a boolean y to B, an observation point By? to X and to O and a variable Y to X such that O(y) = By?, D(By?) = D(Y ) = {0, 1} and L(By?) = L(Y ) = . We impose that By? executes before Y (i.e., By ≺ Y ). We add two conditional relational constraints y ⇒ RY> and ¬y ⇒ RY⊥ to C, where RY> = {(1)} and RY⊥ = {(0)}. 3 We add n − 1 precedence constraints to connect each previous discussed “gadget” encoding a quantified variable of Φ to the next one according to the order in which these variables appear in the quantified part of Φ. 4 For each clause Ci we add a relational constraint ⇒ RSi such that the scope Si contains the three variables embedded in the literals appearing in Ci, whereas the set of tuples is the cross product of the domains of such variables minus the unique tuple falsifying the clause (each of these relations has exactly 23 − 1 tuples).
Lemma 1. Weak controllability of CNCUs is Π2p-complete.
Proof. Hardness: Let Φ ≡ ∀y1, . . . ∀yn, ∃x1, . . . ∃xmϕ a QBF. Solving such an instance of QBF is known to be Π2p-complete. We claim that Φ is satisfiable if and only if QBF2CNCU(Φ) is weakly controllable. Let t a truth value assignment for Φ. Let s(yi) = t(yi) for each yi in Φ. Let α(Xi) = t(xi) for each xi in Φ, α(Yi) = s(yi) for each yi in Φ and α(BYi ) = {0} for each yi in Φ. Let ≺T = Y1 ≺ · · · ≺ Yn ≺ X1 ≺ · · · ≺ Xm. If t |= Φ, then (s, α) |= NΦ. We know that is is true because the constraints of NΦ translate the clauses of Φ. Let now consider the opposite direction. Consider any scenario s and any assignment α. Let ≺T as before. Let t(yi) = s(yi) = α(Yi) for each Yi in NΦ and let t(xi) = α(Xi) for each Xi in NΦ. If (s, α) |= NΦ, then t |= Φ. Again, this is true as the clauses of Φ resemble the relational constraints of N . Membership: A CNCU is weekly controllable iff: for each scenario s there exists a total extension ≺s of ≺ and an assignment αs to the variables satisfying all pertinent constrains. Since the assignment s to the booleans can be seen as a binary string of length |B|, and the total extension ≺s and the assignment αs have a compact encoding, then week controllability of CNCUs is in Π2p by its very definition. Lemma 2. Dynamic controllability of CNCUs is PSPACE-hard.
Proof. Let Φ ≡ ∃x1, . . . ∀y1, ∃x2, ∀y2 . . . ∃xn∀ynϕ a QBF. Solving such an instance of QBF is known to be PSPACE-complete. We claim that Φ is satisfiable iff QBF2CNCU(Φ) is dynamically controllable. The construction t, α, s and ≺T are similar to that discussed in Lemma 1.
Theorem 2. Dynamic controllability of CNCUs is PSPACE-complete.
Proof. Hardness: Proved in Lemma 2. Membership: Algorithm 2 is a polynomial space algorithm to decide dynamic controllability of any CNCU. An AND/OR search tree whose depth size is bounded by a polynomial in the number of variables.
Algorithm 2: CncuDC(N )
Input: A CNCU N = hX , V, D, O, B, O, L, ≺, Ci
Output: Yes, if N is dynamically controllable. No otherwise. 1 CncuDC (N ) 2 Let s, α be an empty scenario and assignment. 3 return Explore(N , X , s, α)
Conclusions and Future Work We classified the computational complexity of weak, strong and dynamic controllability of CNCUs. Weak controllability is Π2p-complete, strong controllability is NP-complete, whereas dynamic controllability is PSPACE-complete.
As future work, we plan to compare with complexity results for other classes of (temporal)-constraint
networks such as those discussed (or employed) in [