Generic complexity of Presburger arithmetic
From MaRDI portal
Publication:848747
DOI10.1007/S00224-008-9120-3zbMATH Open1186.03063OpenAlexW1996544046MaRDI QIDQ848747FDOQ848747
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Linear probing and graphs
- On Worst‐Case to Average‐Case Reductions for NP Problems
- Generic-case complexity, decision problems in group theory, and random walks.
- Title not available (Why is that?)
- Average-case complexity and decision problems in group theory.
- Title not available (Why is that?)
- The halting problem is decidable on a set of asymptotic probability one
Cited In (10)
- ON GENERIC COMPLEXITY OF THE DISCRETE LOGARITHM PROBLEM
- Generic amplification of recursively enumerable sets
- Complexity of Subcases of Presburger Arithmetic
- On mathematical contributions of Paul E. Schupp
- Title not available (Why is that?)
- Generic Complexity of Presburger Arithmetic
- ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM
- The generic complexity of the bounded problem of graphs clustering
- ON GENERIC COMPLEXITY OF THE VALIDITY PROBLEM FOR BOOLEAN FORMULAS
- The generic complexity of the graph triangulation problem
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)
