Complexity of Presburger arithmetic with fixed quantifier dimension

DOI10.1007/BF02679468MaRDI QIDQ1361890zbMATH OpenFDO

Authors Uwe Schöning

Publication date 19 October 1997

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

Full work available at URL https://doi.org/10.1007/BF02679468

zbMATH Keywords

Presburger arithmetic

Mathematics Subject Classification ID

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

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

(39)

• 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
• VC-dimensions of short Presburger formulas
• The computational complexity of integer programming with alternations
• 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
• scientific article; zbMATH DE number 1253963 (Why is no real title available?)
• Separation of complexity classes in Koiran's weak model
• Generic Complexity of Presburger Arithmetic
• An oracle builder's toolkit
• Kolmogorov characterizations of complexity classes
• Enumerating projections of integer points in unbounded polyhedra
• On Presburger arithmetic extended with non-unary counting quantifiers
• scientific article; zbMATH DE number 7407776 (Why is no real title available?)
• On helping by robust oracle machines
• On polynomial-time decidability of k-negations fragments of first-order theories
• Bounding quantification in parametric expansions of Presburger arithmetic
• Locating P/poly optimally in the extended low hierarchy
• On Presburger arithmetic extended with modulo counting quantifiers
• Some consequences of the existnce of pseudorandom generators
• Random languages for nonuniform complexity classes
• Complexity of short generating functions
• Downward translations of equality
• Complexity of short Presburger arithmetic
• A result relating disjunctive self-reducibility to P-immunity
• On the complexity of ranking
• Short Presburger Arithmetic Is Hard
• 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
• Subclasses of Presburger arithmetic and the polynomial-time hierarchy
• Subclasses of Presburger arithmetic and the weak EXP hierarchy
• 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)