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 satisfiability 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 ℙ. 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.

A complexity perspective on entailment of parameterized linear constraints

RUGGIERI, SALVATORE;
2012-01-01

Abstract

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 satisfiability 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 ℙ. 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.
2012
Eirinakis, P; Ruggieri, Salvatore; Subramani, K; Wojciechowski, P. J.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/157790
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact