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

[Stephen Cook]

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
	 
	 Martin:
	 
	 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
	 http://www.cs.nyu.edu/mailman/listinfo/fom