Corps pratique

christophe c · February 2020

Un corps pratique est la donnée de deux fonctions $f,g$ de complexités polynomiales, définies sur $\N^2$ et allant dans $\N$, telles que
1/ $(\N,f,g)$ est un corps.
2/ La question de savoir s'il existe ou pas une solution pour l'équation $E=0$ se résout en temps polynomial sur le nombre de signes pour écrire l'expression $E$, écrite avec des sommes, produits, coefficients entiers écrits en binaire et parenthèses

Question: existe-t-il des corps pratiques?

Commentaires:
1/ J'ai dit qu'on écrit les entiers en base 2, mais je propose la question bis, la même quand il sont écrit en base 1.
2/ Un tel corps est "évidemment" forcément algébriquement clos
3/ L'idéal serait qu'il soit de caractéristique2 et qu'on se restreigne aux équations $E=0$ où tous les coefficients sont des $0$ et des $1$.

In fine, ça fait plusieurs questions proches les unes des autres. On les numérotera avec un point si vous voulez.
Merci par avance pour vos recherches.

Maxtimax · February 2020

Tu peux expliquer ton 2. ? C'est pas clair pour moi pourquoi il pourrait pas y avoir d'élimination des quantificateurs polynomiale :-S

genre si on prend un corps réel clos dénombrable, l'algo est plutôt simple, donc j'ose l'espérer polynomial. Après si ta preuve de 2. fait intervenir la calculabilité de $f,g$, là....

christophe c · February 2020

Ah pardon, oui, dès que tu peux faire "et" dans un corps, tu as un problème NP-complet d'équation "corps-antiennes" :-D car tu peux ramener tout système à une seule équation.

Or dans tout corps non algébriquement clos, tu peux faire "et".

Par exemple, dans $\Q$, $((a=0)$ et $(b=0))$ se dit (ou peut se dire) $a^2=2b^2$. Dans $\R$ tu sais le faire aussi :-D

De manière générale, si tu veux dire $((a=0)$ et $(b=0))$ et que $P$ n'a pas de racine, tu écris

$$P(\frac{a}{b})=0$$

et multiplie par (par exemple) $b^n$ (où $n:=deg(P)$)

Ca te donne $R(a,b)=0$ qui équivaut à $((a=0)$ et $(b=0))$

Ca n'avait en fait rien d'évident, c'est juste que j'en avais parlé il y a peu de temps sur le forum (et même sauf erreur dans ce fil), et que je "faisais comme si" (ce qui est stupide de ma part), la terre entière s'en souvenait :-D

christophe c · February 2020

[large]

C'est la magie de $\frac{0}{0}$

[/large]

Maxtimax · February 2020

ok, il me manque juste "dans tout corps, tu as un problème NP-complet d'équation "corps-antiennes"", qui doit être bien connu, mais je ne le connais pas. Enfin ça me parait toujours bizarre à cause de l'élimination des quantificateurs sur un corps réel clos, mais il doit me manquer un truc.

christophe c · February 2020

Corpantienne j'ai inventé ça veut juste dire une équation de la forme E=0 où E est une expression pas forcément développée en polynôme de plusieurs variables mais qui le serait si on la développait.

Dans TOUT corps dire si un système à une solution est NP complet.

Pour dire r ou s ou w , tu ecris rsw=0 et pour empêcher a et b d'être tout deux nuls, tu peux écrire par exemple ua+vb-1=0

Tu réduis donc SAT.

L'élimination des quantificateurs est tout sauf polynômiale!!!! Même dans F2 (enfin sauf si P=np)

flipflop · February 2020

Marrant ta condition pour dire que $a$ et $b$ ne sont pas tous les deux nuls ! D'ailleurs on peut dire pareil sur un anneau $A$. Donc soit $(a,b) \in A^2$ tel qu'il existe $(u,v) \in A^2$ tel que $au+bc = 1$. Le truc amusant c'est que si un jour tu veux changer d'anneau via un morphisme $\phi : A \to R$ et bien ta condition reste stable pour les images : $\phi(a),\phi(b)$ ne sont pas tous les deux nuls ! Au moins t'es certain pour toute la vie que tes $a$ et $b$ ne seront jamais nul en même temps (enfin s i on arrive a prouver qu'il sont nuls c'est que $0=1$) !

Math Coss · February 2020

Je le note avec une certaine délectation aussi.

Corps pratique

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 8