Real addition and the polynomial hierarchy
From MaRDI portal
(Redirected from Real addition and the polynomial hierarchy)
It is shown that the problem of deciding the truth of a sentence of the first-order theory of real numbers with addition and order given in prenex form with k-1 quantifier alternations is log-complete for the kth level of the polynomial hierarchy, i.e. \(\Sigma^ p_ k\).
Recommendations
Cites work
- A Decision Procedure for the First Order Theory of Real Addition with Order
- scientific article; zbMATH DE number 3497890 (Why is no real title available?)
- scientific article; zbMATH DE number 3261280 (Why is no real title available?)
- Nonlinear regulation: The piecewise linear approach
- On time-space classes and their relation to the theory of real addition
- Remarks on piecewise-linear algebra
- Some characterizations of convex polyhedra
- The complexity of elementary algebra and geometry
- The complexity of logical theories
- The polynomial-time hierarchy
Cited in
(27)- A bibliography of quantifier elimination for real closed fields
- Dominoes and the complexity of subclasses of logical theories
- Saturation and stability in the theory of computation over the reals
- Computing over the reals with addition and order
- The complexity of query evaluation in indefinite temporal constraint databases
- PTIME parametric verification of safety properties for reasonable linear hybrid automata
- Reachability relations of timed pushdown automata
- Erratum to: ``Analyzing restricted fragments of the theory of linear arithmetic
- Temporal reasoning about fuzzy intervals
- scientific article; zbMATH DE number 1670874 (Why is no real title available?)
- Decidability of verification of safety properties of spatial families of linear hybrid automata
- On the complexity of quantified linear systems
- A complexity perspective on entailment of parameterized linear constraints
- scientific article; zbMATH DE number 1418322 (Why is no real title available?)
- Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms
- The unfortunate-flow problem
- Analyzing restricted fragments of the theory of linear arithmetic
- Continuous One-counter Automata
- 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
- Constraint solving for interpolation
- Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy
- Separators in Continuous Petri Nets
- Beyond the Existential Theory of the Reals
- Decidability and complexity of decision problems for affine continuous vass
- Simple sentences that are hard to decide
This page was built for publication: Real addition and the polynomial hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1063589)
