@article{RUGGIERI2014128,
    Abstract = {In this paper, we explore the computational complexity of the conjunctive fragment of the first-order theory of linear arithmetic. Quantified propositional formulas of linear inequalities with (k−1) quantifier alternations are log-space complete in ΣkP or ΠkP depending on the initial quantifier. We show that when we restrict ourselves to quantified conjunctions of linear inequalities, i.e., quantified linear systems, the complexity classes collapse to polynomial time. In other words, the presence of universal quantifiers does not alter the complexity of the linear programming problem, which is known to be in P. Our result reinforces the importance of sentence formats from the perspective of computational complexity.},
    Author = {Ruggieri, Salvatore and Eirinakis, Pavlos and Subramani, K. and Wojciechowski, Piotr},
    File = {1-s2.0-S0304397513005781-main (0) (0) - a - a - e.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Keywords = {Quantified linear systems, Theory of real numbers with addition, Complexity classes},
    Pages = {128 - 134},
    Title = {On the complexity of quantified linear systems},
    URL = {http://www.sciencedirect.com/science/article/pii/S0304397513005781},
    Volume = {518},
    Year = {2014},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397513005781},
    bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2013.08.001},
    date-added = {2019-03-12 20:22:59 +0100},
    date-modified = {2019-03-12 20:22:59 +0100},
    doi = {10.1016/j.tcs.2013.08.001}
}

@article{RUGGIERI2014128, Abstract = {In this paper, we explore the computational complexity of the conjunctive fragment of the first-order theory of linear arithmetic. Quantified propositional formulas of linear inequalities with (k−1) quantifier alternations are log-space complete in ΣkP or ΠkP depending on the initial quantifier. We show that when we restrict ourselves to quantified conjunctions of linear inequalities, i.e., quantified linear systems, the complexity classes collapse to polynomial time. In other words, the presence of universal quantifiers does not alter the complexity of the linear programming problem, which is known to be in P. Our result reinforces the importance of sentence formats from the perspective of computational complexity.}, Author = {Ruggieri, Salvatore and Eirinakis, Pavlos and Subramani, K. and Wojciechowski, Piotr}, File = {1-s2.0-S0304397513005781-main (0) (0) - a - a - e.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Keywords = {Quantified linear systems, Theory of real numbers with addition, Complexity classes}, Pages = {128 - 134}, Title = {On the complexity of quantified linear systems}, URL = {http://www.sciencedirect.com/science/article/pii/S0304397513005781}, Volume = {518}, Year = {2014}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397513005781}, bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2013.08.001}, date-added = {2019-03-12 20:22:59 +0100}, date-modified = {2019-03-12 20:22:59 +0100}, doi = {10.1016/j.tcs.2013.08.001} }