Generic complexity of Presburger arithmetic

DOI10.1007/S00224-008-9120-3MaRDI QIDQ848747zbMATHOpenAlexFDO

Authors Alexander Rybalov

Publication date 5 March 2010

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

Full work available at URL https://doi.org/10.1007/s00224-008-9120-3

zbMATH Keywords

Presburger arithmeticgeneric complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Generic Complexity of Presburger Arithmetic
• Complexity of Subcases of Presburger Arithmetic
• Generic complexity of first-order theories
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Complexity of short Presburger arithmetic

Cites work

• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• Average-case complexity and decision problems in group theory.
• Generic-case complexity, decision problems in group theory, and random walks.
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Linear probing and graphs
• On Worst‐Case to Average‐Case Reductions for NP Problems
• The halting problem is decidable on a set of asymptotic probability one

Cited in

(12)

• ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM
• Generic amplification of recursively enumerable sets
• The generic complexity of the bounded problem of graphs clustering
• Generic complexity of first-order theories
• On generic complexity of the discrete logarithm problem
• Generic Complexity of Presburger Arithmetic
• The generic complexity of the graph triangulation problem
• On generic complexity of the validity problem for Boolean formulas
• Complexity of Subcases of Presburger Arithmetic
• scientific article; zbMATH DE number 1253963 (Why is no real title available?)
• On mathematical contributions of Paul E. Schupp
• Complexity of short Presburger arithmetic

This page was built for publication: Generic complexity of Presburger arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q848747)