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  for some constant , where  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.

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.