Accession Number : AD0775004

Title :   Super-Exponential Complexity of Presburger Arithmetic.

Descriptive Note : Technical memo.,


Personal Author(s) : Fischer,Michael J. ; Rabin,Michael O.

Report Date : FEB 1974

Pagination or Media Count : 27

Abstract : Lower bounds are established on the computational complexity of the decision problem and on the inherent lengths of proofs for two classical decidable theories of logic: the first order theory of the real numbers under addition, and Presburger arithmetic -- the first order theory of addition on the natural numbers. There is a fixed constant c > 0 such that for every (non-deterministic) decision procedure for determining the truth of sentences of real addition and for all sufficiently large n, there is a sentence of length n for which the decision procedure runs for more than (2 sup (cn)) steps. In the case of Presburger arithmetic, the corresponding bound is 2 sup (2 sup (cn)). These bounds apply also to the minimal lengths of proofs for any complete axiomatization in which the axioms are easily recognized. (Author)

Descriptors :   *Mathematical logic, *Addition, Groups(Mathematics), Number theory, Algorithms, Theorems

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE