[FOM] Complexity of the elementary theory of subfields of the reals

[Vaughan Pratt]

(Adding the missing word "reals" to my subject may disconnect the 
intended thread, probably not a big loss.)

To triangulate my (thus far unanswered) question with some more data 
points: besides Kossovski's result that I cited at the quantifier-free 
negationless end, there is at the other, elementary, end the (recently 
discussed) result by Julia Robinson of the undecidability of the 
elementary theory of the rational field, and Tarski's decidability of 
that for the algebraic reals.

1.  For the elementary theories, what significant transitions are there 
between the rationals and the algebraic reals?  In particular:

(i) Does Tarski's result obtain uniformly over the interval from the 
quadratic irrationals to the algebraic reals?

(ii) Does Robinson's result obtain uniformly over all extensions of Q of 
finite transcendence degree?

(iii) What of interest lies between finite transcendence degree over Q 
and the quadratic irrationals?

2.  Barring refinements of 1 I'm not expecting, there ought to be just 
two cases, undecidable and decidable.  What happens in the passage to 
the quantifier-free case?  Is there more diversity?  I have no 
expectations about how many cases there are along the same spectrum.

These are consumer questions, not producer.  I'd like to be able to use 
this information but I'm not expecting to be able to contribute anything 
to it.

Vaughan Pratt

Vaughan Pratt wrote:
> How does the computational complexity of the elementary (resp. 
> quantifier-free resp. negationless) theory of field extensions of the 
> rationals vary with increasing dimension?  What happens at the quadratic 
> irrationals?  These are of interest as number systems for affine and 
> Euclidean geometry at all finite dimensions.  Kossovsky has shown that 
> the problem in his title [1] is in EXPTIME and proposes that theory as 
> "a base of constructive mathematics."
> 
> [1] Kossovski, N., (2001) Computational complexity of quantifier-free 
> negationless theory of field of rational numbers, Annals of Pure and 
> Applied Logic, 113:1, 175-180.
> 
> Vaughan Pratt