Complexity of Weak, Strong and Dynamic Controllability of CNCUs

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). Before the execution of the CNCU starts (i.e., the online assignment of values to variables), we do not know completely 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 a strategy to execute a CNCU possibly differently depending on how the uncontrollable part is behaving. We prove that weak controllability is $Pi_2^p$-complete, strong controllability is NP-complete and dynamic controllability is PSPACE-complete.