Generic complexity of Presburger arithmetic

DOI10.1007/s00224-008-9120-3zbMath1186.03063OpenAlexW1996544046MaRDI QIDQ848747

Alexander N. 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)

Related Items (7)

Generic amplification of recursively enumerable sets ⋮ 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 ⋮ On mathematical contributions of Paul E. Schupp ⋮ The generic complexity of the bounded problem of graphs clustering ⋮ The generic complexity of the graph triangulation problem

Cites Work

• Unnamed Item
• Unnamed Item
• Average-case complexity and decision problems in group theory.
• Linear probing and graphs
• Generic-case complexity, decision problems in group theory, and random walks.
• The halting problem is decidable on a set of asymptotic probability one
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• On Worst‐Case to Average‐Case Reductions for NP Problems

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