Generic complexity of Presburger arithmetic

DOI10.1007/S00224-008-9120-3MaRDI QIDQ848747zbMATH OpenOpenAlexFDO

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

generic complexityPresburger arithmetic

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• 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)

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

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)