Complexity of Presburger arithmetic with fixed quantifier dimension

DOI10.1007/BF02679468zbMATH Open0872.68048MaRDI QIDQ1361890FDOQ1361890

Authors: Uwe Schöning 

Publication date: 19 October 1997

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

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

zbMATH Keywords

Presburger arithmetic

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Integer Programming with a Fixed Number of Variables
• The polynomial-time hierarchy
• The complexity of logical theories
• Complete sets and the polynomial-time hierarchy
• The computational complexity of logical theories
• Presburger arithmetic with bounded quantifier alternation
• Title not available (Why is that?)
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• Complexity of Subcases of Presburger Arithmetic

Cited In (36)

• Robust machines accept easy sets
• Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
• Polynomial terse sets
• Complexity of Subcases of Presburger Arithmetic
• Enumerative counting is hard
• The Computational Complexity of Integer Programming with Alternations
• VC-dimensions of short Presburger formulas
• On characterizations of the class PSPACE/poly
• Generic complexity of Presburger arithmetic
• Turing machines with few accepting computations and low sets for PP
• Logarithmic advice classes
• Title not available (Why is that?)
• Generic Complexity of Presburger Arithmetic
• Separation of complexity classes in Koiran's weak model
• On Presburger arithmetic extended with non-unary counting quantifiers
• An oracle builder's toolkit
• Kolmogorov characterizations of complexity classes
• Presburger arithmetic, rational generating functions, and quasi-polynomials
• Title not available (Why is that?)
• On helping by robust oracle machines
• Bounding quantification in parametric expansions of Presburger arithmetic
• Locating \(P\)/poly optimally in the extended low hierarchy
• Some consequences of the existnce of pseudorandom generators
• Random languages for nonuniform complexity classes
• Downward translations of equality
• Short Presburger Arithmetic Is Hard
• A result relating disjunctive self-reducibility to P-immunity
• On the complexity of ranking
• Graph isomorphism is in the low hierarchy
• Probabilistic complexity classes and lowness
• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
• COMPLEXITY OF SHORT GENERATING FUNCTIONS
• Subclasses of Presburger arithmetic and the polynomial-time hierarchy
• Enumerating Projections of Integer Points in Unbounded Polyhedra
• Dominoes and the complexity of subclasses of logical theories
• If not empty, NP-P is topologically large

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)