It was recently shown that the theories of generic algebraic curves converge to a limit theory as their degrees go to infinity. In this paper we give quantitative versions of this result and other similar results. In particular, we show that generic curves of degree higher than 22r cannot be distinguished by a first-order formula of quantifier rank r. A decision algorithm for the limit theory then follows easily. We also show that in this theory all formulas are equivalent to (...) boolean combinations of existential formulas, and give a quantitative version of this result. (shrink)

Let f be a function from N to N that can not be computed in polynomial time, and let a be an element of a differential field K of characteristic 0. The problem of large powers is the set of tuples x̄ = (x 1 ,..., x n ) of K so that x 1 = a f(n) , and the problem of large roots is the set of tuples x̄ of K so that x f(n) 1 = a. These (...) are two examples of problems that the use of derivation does not allow to solve quicker. We show that the problem of large roots is not polynomial for the differential field K, even if we use a polynomial number of parameters, and that the problem of large powers is not polynomial for the differential field K, even for non-uniform complexity. The proofs use the polynomial stability (i.e., the elimination of parameters) of field of characteristic 0, shown by L. Blum. F. Cucker. M. Shub and S. Smale, and the reduction lemma, that transforms a differential polynomial in variables x̄ into a polynomial in variables x̄. and their derivatives. (shrink)

A notion of complexity for an arbitrary structure was defined in the book of Poizat Les petits cailloux (1995): we can define P and NP problems over a differential field K. Using the Witness Theorem of Blum et al., we prove the P-stability of the theory of differential fields: a P problem over a differential field K is still P when restricts to a sub-differential field k of K. As a consequence, if P = NP over some differentially closed field (...) K, then P = NP over any differentially closed field and over any algebraically closed field. (shrink)