Generic complexity of Presburger arithmetic
type: Item
instance of: scholarly article
title: Generic complexity of Presburger arithmetic
zbMATH Open document ID: 1186.03063
author: Alexander Rybalov
published in: Theory of Computing Systems
publication date: 2010-03-05T00:00:00Z
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5677846
zbMATH Keywords: generic complexity
zbMATH Keywords: Presburger arithmetic
MaRDI profile type: Publication
full work available at URL: s00224-008-9120-3
OpenAlex ID: W1996544046
cites work: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
cites work: On Worst‐Case to Average‐Case Reductions for NP Problems
cites work: Q3413362
cites work: Q4082296
cites work: The halting problem is decidable on a set of asymptotic probability one
cites work: Generic-case complexity, decision problems in group theory, and random walks.
cites work: Average-case complexity and decision problems in group theory.
cites work: Linear probing and graphs
DOI: 10.1007/S00224-008-9120-3
description: scientific article; zbMATH DE number 5677846