On the complexity of quantified linear systems

DOI10.1016/J.TCS.2013.08.001MaRDI QIDQ391791zbMATH OpenOpenAlexFDO

Authors Salvatore Ruggieri, Pavlos Eirinakis, K. Subramani, Piotr Wojciechowski

Publication date 13 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.08.001

zbMATH Keywords

complexity classesquantified linear systemstheory of real numbers with addition

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Recommendations

• Analyzing restricted fragments of the theory of linear arithmetic
• On the complexity of quantified integer programming
• The complexity of problems for quantified constraints
• Computational complexity of quantified Boolean formulas with fixed maximal deficiency
• Computational complexity of arithmetical sentences

Cites work

• A Decision Procedure for the First Order Theory of Real Addition with Order
• A new approach for automatic theorem proving in real geometry
• Computational Difficulties of Bilevel Linear Programming
• Efficient solving of quantified inequality constraints over the real numbers
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3825556 (Why is no real title available?)
• scientific article; zbMATH DE number 4083375 (Why is no real title available?)
• scientific article; zbMATH DE number 1302474 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• New results on quantifier elimination over real closed fields and applications to constraint databases
• On a decision procedure for quantified linear programs
• On the combinatorial and algebraic complexity of quantifier elimination
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Partial cylindrical algebraic decomposition for quantifier elimination
• QEPCAD B
• Real addition and the polynomial hierarchy
• Real quantifier elimination is doubly exponential
• The complexity of linear problems in fields
• The complexity of logical theories
• The computational complexity of multi-level linear programs
• The polynomial hierarchy and a simple model for competitive analysis

Cited in

(2)

• Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates
• Analyzing restricted fragments of the theory of linear arithmetic

Describes a project that uses

Uses Software

• QEPCAD
• REDLOG
• RSOLVER

This page was built for publication: On the complexity of quantified linear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q391791)