Polynomial stability of differential fields

Authors
Citation
N. Portier, Polynomial stability of differential fields, J SYMB LOG, 64(2), 1999, pp. 803-816
Citations number
12
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF SYMBOLIC LOGIC
ISSN journal
00224812 → ACNP
Volume
64
Issue
2
Year of publication
1999
Pages
803 - 816
Database
ISI
SICI code
0022-4812(199906)64:2<803:PSODF>2.0.ZU;2-7
Abstract
A notion of complexity for an arbitrary structure was defined in the book o f 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 t he P-stability of the theory of differential fields: a P problem over a dif ferential field K is still P when restricts to a sub-differential field It 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.