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)

We reduce to a standard circuit-size complexity problem a relativisation of the $P = NP$ question that we believe to be connected with the same question in the model for computation over the reals defined by L. Blum, M. Shub, and S. Smale. On this occasion, we set the foundations of a general theory for computation over an arbitrary structure, extending what these three authors did in the case of rings.