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.