Generic Complexity of Presburger Arithmetic
Generic Complexity of Presburger Arithmetic
复制标题
普雷斯堡算法的一般复杂性
DOI：
10.1007/s00224-008-9120-3
复制
发表时间：
2007
影响因子：
0.5
通讯作者：
A. Rybalov
中科院分区：
文献类型：
--
作者：
A. Rybalov
Fischer 和 Rabin 在（SIAM-AMS 应用数学研讨会论文集，第 7 卷，第 27-41 页，1974 年）中证明，普雷斯堡算术的决策问题至少具有双指数最坏情况复杂性（对于确定性和非确定性图灵机）。在卡波维奇等人中。 (J. Algebra 264(2):665–694, 2003）发展了一般情况复杂性理论，其中算法问题是在“大多数”输入而不是所有输入的集合上研究的。一个问题是，是否存在更有效的（例如，多项式）泛型算法，可以在一组渐近密度 1 的封闭公式上进行普雷斯堡算法决策。我们在本文中证明，在渐近密度指数收敛到 1 的输入集（所谓的强泛型集）上，不存在正确工作的指数泛型决策算法。
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).