Stabilite Polynomiale des Corps Differentiels
Portier, Natacha
J. Symbolic Logic, Tome 64 (1999) no. 1, p. 803-816 / Harvested from Project Euclid
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.
Publié le : 1999-06-14
Classification:  Complexity,  Differential Field,  Definissability of Types,  Stability
@article{1183745811,
     author = {Portier, Natacha},
     title = {Stabilite Polynomiale des Corps Differentiels},
     journal = {J. Symbolic Logic},
     volume = {64},
     number = {1},
     year = {1999},
     pages = { 803-816},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/1183745811}
}
Portier, Natacha. Stabilite Polynomiale des Corps Differentiels. J. Symbolic Logic, Tome 64 (1999) no. 1, pp.  803-816. http://gdmltest.u-ga.fr/item/1183745811/