[FOM] Re: query about complexity of the theory of [R,+, < ]

Stephen Cook sacook at cs.toronto.edu
Mon Nov 3 18:08:00 EST 2003

To be more precise, the Ferrante/Rackoff upper bound is
*space* 2^{cn} for some c, and the Fischer/Rabin lower bound
is nondeterministic time 2^{c'n} for some c'.

The space upper bound implies a time upper bound of 2^{2^{cn}}
and of course the time lower bound also applies to deterministic
Turing machines.

Stephen Cook
	 The theory of nontrivial divisible ordered abelian groups is
	 complete. So the ordered groups of the reals and the rationals
	 have the same decidable theory. [This is in section 3.1 of my
	 Model Theory text.]
	 Ferrante and Rackoff gave a O(2^{cn}) decision procedure for some c,
	 while Fischer and Rabin showed that for some constants d there
	 is no O(2^{dn}) algorithm.
	 My recollection is that even for stronger theories like the theory
	 of real closed fields or the theory of the real field with
	 exponentiation the Fischer-Rabin lower bounds were the best known.
	 I would be interested if anyone knows of any better results.
	 Dave Marker
	 FOM mailing list
	 FOM at cs.nyu.edu

More information about the FOM mailing list