Complexity of Presburger arithmetic with fixed quantifier dimension
From MaRDI portal
Publication:1361890
Recommendations
- Subclasses of Presburger arithmetic and the polynomial-time hierarchy
- Complexity of Subcases of Presburger Arithmetic
- Subclasses of Presburger arithmetic and the weak EXP hierarchy
- On Presburger arithmetic extended with modulo counting quantifiers
- Dominoes and the complexity of subclasses of logical theories
Cites work
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- scientific article; zbMATH DE number 3501006 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- Complete sets and the polynomial-time hierarchy
- Complexity of Subcases of Presburger Arithmetic
- Integer Programming with a Fixed Number of Variables
- Presburger arithmetic with bounded quantifier alternation
- The complexity of Presburger arithmetic with bounded quantifier alternation depth
- The complexity of logical theories
- The computational complexity of logical theories
- The polynomial-time hierarchy
Cited in
(38)- Subclasses of Presburger arithmetic and the polynomial-time hierarchy
- Locating \(P\)/poly optimally in the extended low hierarchy
- Enumerative counting is hard
- Complexity of short generating functions
- Robust machines accept easy sets
- Turing machines with few accepting computations and low sets for PP
- A result relating disjunctive self-reducibility to P-immunity
- Bounding quantification in parametric expansions of Presburger arithmetic
- Some consequences of the existnce of pseudorandom generators
- Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
- On the complexity of ranking
- The computational complexity of integer programming with alternations
- An oracle builder's toolkit
- Generic Complexity of Presburger Arithmetic
- Downward translations of equality
- Polynomial terse sets
- Subclasses of Presburger arithmetic and the weak EXP hierarchy
- Probabilistic complexity classes and lowness
- Kolmogorov characterizations of complexity classes
- Short Presburger Arithmetic Is Hard
- Graph isomorphism is in the low hierarchy
- If not empty, NP-P is topologically large
- Logarithmic advice classes
- On Presburger arithmetic extended with modulo counting quantifiers
- Separation of complexity classes in Koiran's weak model
- Generic complexity of Presburger arithmetic
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
- On characterizations of the class PSPACE/poly
- Complexity of Subcases of Presburger Arithmetic
- scientific article; zbMATH DE number 1253963 (Why is no real title available?)
- Random languages for nonuniform complexity classes
- VC-dimensions of short Presburger formulas
- Dominoes and the complexity of subclasses of logical theories
- Complexity of short Presburger arithmetic
- Enumerating projections of integer points in unbounded polyhedra
- On helping by robust oracle machines
- On Presburger arithmetic extended with non-unary counting quantifiers
- scientific article; zbMATH DE number 7407776 (Why is no real title available?)
This page was built for publication: Complexity of Presburger arithmetic with fixed quantifier dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1361890)
