Complexity of Presburger arithmetic with fixed quantifier dimension

DOI10.1007/BF02679468zbMath0872.68048MaRDI QIDQ1361890

Uwe Schoening

Publication date: 19 October 1997

Published in: Theory of Computing Systems (Search for Journal in Brave)

zbMATH Keywords

Presburger arithmetic

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (29)

Separation of complexity classes in Koiran's weak model ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ On helping by robust oracle machines ⋮ Polynomial terse sets ⋮ On characterizations of the class PSPACE/poly ⋮ Short Presburger Arithmetic Is Hard ⋮ Subclasses of Presburger arithmetic and the polynomial-time hierarchy ⋮ Graph isomorphism is in the low hierarchy ⋮ Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials ⋮ An oracle builder's toolkit ⋮ The Computational Complexity of Integer Programming with Alternations ⋮ On Presburger arithmetic extended with non-unary counting quantifiers ⋮ Downward translations of equality ⋮ Robust machines accept easy sets ⋮ Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems ⋮ A result relating disjunctive self-reducibility to P-immunity ⋮ On the complexity of ranking ⋮ Random languages for nonuniform complexity classes ⋮ Enumerating Projections of Integer Points in Unbounded Polyhedra ⋮ Turing machines with few accepting computations and low sets for PP ⋮ Logarithmic advice classes ⋮ If not empty, NP-P is topologically large ⋮ Probabilistic complexity classes and lowness ⋮ Some consequences of the existnce of pseudorandom generators ⋮ Enumerative counting is hard ⋮ COMPLEXITY OF SHORT GENERATING FUNCTIONS ⋮ Unnamed Item ⋮ Kolmogorov characterizations of complexity classes ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of logical theories
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• The computational complexity of logical theories
• Integer Programming with a Fixed Number of Variables
• Complexity of Subcases of Presburger Arithmetic
• Presburger arithmetic with bounded quantifier alternation

This page was built for publication: Complexity of Presburger arithmetic with fixed quantifier dimension