Corps pratique
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.
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.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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à....
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
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)