[FOM] Complexity of the elementary theory of subfields of the reals
Vaughan Pratt
pratt at cs.stanford.edu
Wed Sep 26 04:17:37 EDT 2007
(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
More information about the FOM
mailing list