Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
155 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Corps pratique

Envoyé par christophe c 
Corps pratique
il y a cinq semaines
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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 1 fois. La dernière correction date de il y a cinq semaines et a été effectuée par AD.
Re: corps pratique
il y a cinq semaines
Tu peux expliquer ton 2. ? C'est pas clair pour moi pourquoi il pourrait pas y avoir d'élimination des quantificateurs polynomiale confused smiley

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à....

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: corps pratique
il y a cinq semaines
Ah pardon, oui, dès que tu peux faire "et" dans un corps, tu as un problème NP-complet d'équation "corps-antiennes" grinning smiley 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 grinning smiley

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 grinning smiley

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 1 fois. La dernière correction date de il y a cinq semaines et a été effectuée par christophe c.
Re: corps pratique
il y a cinq semaines
C'est la magie de $\frac{0}{0}$


Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 1 fois. La dernière correction date de il y a cinq semaines et a été effectuée par christophe c.
Re: corps pratique
il y a cinq semaines
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.

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: corps pratique
il y a cinq semaines
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)

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: corps pratique
il y a cinq semaines
avatar
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$) !



Edité 1 fois. La dernière correction date de il y a cinq semaines et a été effectuée par flipflop.
Re: corps pratique
il y a cinq semaines
Je le note avec une certaine délectation aussi.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 140 501, Messages: 1 373 654, Utilisateurs: 25 580.
Notre dernier utilisateur inscrit thmoas.


Ce forum
Discussions: 2 208, Messages: 43 844.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page