Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-24T22:39:20.883Z Has data issue: false hasContentIssue false
  • English
  • Français

Stabilité polynômiale des corps différentiels

Published online by Cambridge University Press:  12 March 2014

Natacha Portier
Natacha Portier*
Affiliation:
Institut Girard Desargues- Upres-A 5028 Du CNRS, Université Claude Bernard Lyon-I, Bâtiment Du Doyen Jean Braconnier (101), 43, Boulevard Du 11 Novembre 1918, 69 622 Villeurbanne Cedex, France E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

ComplexityDifferential FieldDefinissability of TypesStability
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 64 , Issue 2 , June 1999 , pp. 803 - 816
Copyright
Copyright © Association for Symbolic Logic 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Blum, Lenore, Generalized algebraic structures: A model theoretic approach, Ph.D. thesis , Massachussets Institute of Technology, 1968.Google Scholar
[2] Blum, Lenore, Cucker, Felipe, Shub, Mike, et Smale, Steve, Algebraic settings for the problem “P ≠ NP?”, Mathematics of numerical analysis (Renegar, et al., editor), Lectures in Applied Mathematics, vol. 32, 1996, pp. 125–144.Google Scholar
[3] Blum, Lenore, Shub, Mike, et Smale, Steve, On a theorey of computation and complexity over real numbers: NP-completeness, recursive functions and universal machines, Bulletin of the Americal Mathematical Society, vol. 21 (1989), no. 1, pp. 1–46.Google Scholar
[4] Chapuis, Olivier et Koiran, Pascal, Saturation and stability in the theory of computation over the reals, Prepublications de l' Institut Girard Desargues, 1997.Google Scholar
[5] Goode, John B., Accessible telephone directories, this Journal, vol. 59 (1993), no. 1, pp. 92–105.Google Scholar
[6] Kolchin, E., Differentially Algebra and Algebraic Groups, Academic Press, 1973.Google Scholar
[7] Marker, D., Messmer, M., et Pillay, A., Model Theory of Fields, Lecture Notes in Logic, Springer, 1996.Google Scholar
[8] Michaux, Christian, P ≠ NP over the non-standard reals implies P ≠ NP over R, Theoretical Computer Science (1994), no. 133, pp. 95–104.Google Scholar
[9] Poizat, B., Cours de théorie des modéles, Nur Al-Mantiq Walma'rifah, 1985.Google Scholar
[10] Poizat, B., Les petits cailloux, aleas éditeur, 1995.Google Scholar
[11] Robinson, Abraham, On the concept of a differentially closed field, Bulletin of Research of the Israel Council, vol. F8 (1959), pp. 113–128.Google Scholar
[12] Wood, Carol, The model theory of differential fields revisited, Israel Journal of Mathematics, vol. 25 (1976), pp. 331–352.CrossRefGoogle Scholar