Generic Complexity of Presburger Arithmetic |
| |
Authors: | Alexander N Rybalov |
| |
Affiliation: | 1. Omsk Branch of the Institute of Mathematics of SB RAS, Pevtsova, 13, Omsk, 644099, Russia
|
| |
Abstract: | Fischer and Rabin proved in (Proceedings of the SIAM-AMS Symposium in Applied Mathematics, vol. 7, pp. 27–41, 1974) that the decision problem for Presburger Arithmetic has at least double exponential worst-case complexity (for deterministic
and for nondeterministic Turing machines). In Kapovich et al. (J. Algebra 264(2):665–694, 2003) a theory of generic-case complexity was developed, where algorithmic problems are studied on “most” inputs instead of set
of all inputs. A question rises about existing of more efficient (say, polynomial) generic algorithm deciding Presburger Arithmetic
on a set of closed formulas of asymptotic density 1. We prove in this paper that there is not an exponential generic decision
algorithm working correctly on an input set of asymptotic density exponentially converging to 1 (so-called strongly generic
sets). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|