Article contents
Stabilité polynômiale des corps différentiels
Published online by Cambridge University Press: 12 March 2014
Abstract
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.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 1999
References
REFERENCES
- 3
- Cited by