TOPICS
Search

Presburger Arithmetic


Presburger arithmetic is the first-order theory of the natural numbers containing addition but no multiplication. It is therefore not as powerful as Peano arithmetic. However, it is interesting because unlike the case of Peano arithmetic, there exists an algorithm that can decide if any given statement in Presburger arithmetic is true (Presburger 1929). No such algorithm exists for general arithmetic as a consequence of Robinson and Tarski's negative answer to the decision problem. Presburger (1929) also proved that his arithmetic is consistent (does not contain contradictions) and complete (every statement can either be proven or disproven), which is false for Peano arithmetic as a consequence of Gödel's first incompleteness theorem.

Fischer and Rabin (1974) proved that every algorithm which decides the truth of Presburger statements has a running time of at least 2^(2^(cn)) for some constant c, where n is the length of the Presburger statement. Therefore, the problem is one of the few currently known that provably requires more than polynomial run time.


See also

Decision Problem, Gödel's First Incompleteness Theorem, Gödel's Second Incompleteness Theorem, Peano Arithmetic, Peano's Axioms

Explore with Wolfram|Alpha

References

Fischer, M. J. and Rabin, M. O. "Super-Exponential Complexity of Presburger Arithmetic." Complexity of Computation. Proceedings of a Symposium in Applied Mathematics of the American Mathematical Society and the Society for Industrial and Applied Mathematics. Held in New York, April 18-19, 1973 (Ed. R. M. Karp). Providence, RI: Amer. Math. Soc., pp. 27-41, 1974.Presburger, M. "Ueber die Vollstaendigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt." In Comptes Rendus du I congrés de Mathématiciens des Pays Slaves. Warsaw, Poland: pp. 92-101, 1929.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 1143 and 1152, 2002.

Referenced on Wolfram|Alpha

Presburger Arithmetic

Cite this as:

Weisstein, Eric W. "Presburger Arithmetic." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PresburgerArithmetic.html

Subject classifications