Generic complexity of Presburger arithmetic

DOI10.1007/S00224-008-9120-3zbMATH Open1186.03063OpenAlexW1996544046MaRDI QIDQ848747FDOQ848747

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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.
• Average-case complexity and decision problems in group theory.
• The halting problem is decidable on a set of asymptotic probability one

Cited In (8)

• ON GENERIC COMPLEXITY OF THE DISCRETE LOGARITHM PROBLEM
• Generic amplification of recursively enumerable sets
• On mathematical contributions of Paul E. Schupp
• Title not available (Why is that?)
• 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)