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

Vaughan Pratt pratt at cs.stanford.edu
Tue Sep 18 18:25:35 EDT 2007

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

More information about the FOM mailing list