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.
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.
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.
