Stabilité polynômiale des corps différentiels.



Résumé


Dans son livre Les petits cailloux (1995), Poizat a défini une notion de complexité dans une structure quelconque. En particulier, on peut définir les classes P et NP sur un corps différentiel. En utilisant le théorème des témoins de Blum et al., nous montrons la P-stabilité de la théorie des corps différentiels de caractéristique nulle : si X est un problème P sur un corps différentiel K, sa restriction à un sous-corps différentiel k de K est P sur k. Nous en déduisons que la réponse à la question P=NP? a la même réponse dans tous les corps différentiellement clos de caractéristique nulle.

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.