主题
Search

普莱斯伯格算术

普莱斯伯格算术是自然数的一阶理论，包含加法但没有乘法。 因此，它不如 皮亚诺算术 强大。 然而，它很有趣，因为与 皮亚诺算术 的情况不同，存在一种算法可以判定普莱斯伯格算术中的任何给定陈述是否为真（Presburger 1929）。 由于罗宾逊和塔斯基对 判定问题 的否定回答，对于一般算术不存在这样的算法。 Presburger (1929) 还证明了他的算术是一致的（不包含矛盾）和完备的（每个陈述都可以被证明或证伪），这对于 皮亚诺算术 来说是错误的，这是 哥德尔第一不完备性定理 的结果。

Fischer 和 Rabin (1974) 证明，每种判定普莱斯伯格语句真假的算法的运行时间至少为 2^(2^(cn))，其中 c 为某个常数，n 为普莱斯伯格语句的长度。 因此，这个问题是目前已知的少数几个被证明需要超过多项式运行时间的问题之一。

另请参阅

判定问题, 哥德尔第一不完备性定理, 哥德尔第二不完备性定理, 皮亚诺算术, 皮亚诺公理

使用 Wolfram|Alpha 探索

参考文献

Fischer, M. J. 和 Rabin, M. O. "普莱斯伯格算术的超指数复杂性。" 计算复杂性。美国数学会和工业与应用数学学会应用数学研讨会论文集。1973 年 4 月 18-19 日在纽约举行 (Ed. R. M. Karp)。 Providence, RI: Amer. Math. Soc., pp. 27-41, 1974。Presburger, M. "关于整数算术的某个系统的完备性，其中加法是唯一突出的运算。" In 斯拉夫国家数学家第一次代表大会记录。 华沙，波兰：pp. 92-101, 1929。Wolfram, S. 一种新的科学。 Champaign, IL: Wolfram Media, pp. 1143 和 1152, 2002。

在 Wolfram|Alpha 中引用

普莱斯伯格算术

请引用为

Weisstein, Eric W. "普莱斯伯格算术。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PresburgerArithmetic.html

主题分类