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

[Vaughan Pratt]

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