[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