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 Πp2-complete, strong controllability is NP-complete and dynamic controllability is PSPACE-complete.
Complexity of weak, strong and dynamic controllability of CNCUs
Zavatteri, Matteo
;
2020
Abstract
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 Πp2-complete, strong controllability is NP-complete and dynamic controllability is PSPACE-complete.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
