Real addition and the polynomial hierarchy
From MaRDI portal
Publication:1063589
DOI10.1016/0020-0190(85)90076-6zbMath0575.03030OpenAlexW2035496804MaRDI QIDQ1063589
Publication date: 1985
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(85)90076-6
Related Items (23)
Erratum to: ``Analyzing restricted fragments of the theory of linear arithmetic ⋮ Computing over the reals with addition and order ⋮ A bibliography of quantifier elimination for real closed fields ⋮ Temporal reasoning about fuzzy intervals ⋮ The complexity of query evaluation in indefinite temporal constraint databases ⋮ Dominoes and the complexity of subclasses of logical theories ⋮ Constraint solving for interpolation ⋮ On the complexity of quantified linear systems ⋮ Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy ⋮ Separators in Continuous Petri Nets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Decidability of Verification of Safety Properties of Spatial Families of Linear Hybrid Automata ⋮ PTIME parametric verification of safety properties for reasonable linear hybrid automata ⋮ Reachability relations of timed pushdown automata ⋮ A complexity perspective on entailment of parameterized linear constraints ⋮ Analyzing restricted fragments of the theory of linear arithmetic ⋮ A survey of computational complexity results in systems and control ⋮ A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems ⋮ Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning ⋮ Saturation and stability in the theory of computation over the reals ⋮ Simple sentences that are hard to decide ⋮ Continuous One-counter Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Some characterizations of convex polyhedra
- The complexity of elementary algebra and geometry
- On time-space classes and their relation to the theory of real addition
- The complexity of logical theories
- Remarks on piecewise-linear algebra
- The polynomial-time hierarchy
- Nonlinear regulation: The piecewise linear approach
- A Decision Procedure for the First Order Theory of Real Addition with Order
This page was built for publication: Real addition and the polynomial hierarchy
