PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Eirinakis P., Ruggieri S., Subramani K., Wojciechowski P. A complexity perspective on entailment of parameterized linear constraints. In: CONSTRAINTS, vol. 17 (4) pp. 461 - 487. Springer, 2012.
 
 
Abstract
(English)
Extending linear constraints by admitting parameters allows for more abstract problem modeling and reasoning. A lot of focus has been given to conducting research that demonstrates the usefulness of parameterized linear constraints and implementing tools that utilize their modeling strength. However, there is no approach that considers basic theoretical tools related to such constraints that allow for reasoning over them. Hence, in this paper we introduce satisf iability with respect to polyhedral sets and entailment for the class of parameterized linear constraints. In order to study the computational complexities of these problems, we relate them to classes of quantified linear implications. The problem of satisfiability with respect to polyhedral sets is then shown to be co-NP hard. The entailment problem is also shown to be co-NP hard in its general form. Nevertheless, we characterize some subclasses for which this problem is in P. Furthermore, we examine a weakening and a strengthening extension of the entailment problem. The weak entailment problem is proved to be NP complete. On the other hand, the strong entailment problem is shown to be co-NP hard.
URL: http://link.springer.com/article/10.1007%2Fs10601-012-9127-x
DOI: 10.1007/s10601-012-9127-x
Subject Entailment
Parameterized linear constraint
Quantified linear program
Quantified linear implication
Computational complexity
Polynomial algorithm
D.3.3 Language Constructs and Features


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional