J'aurais résolu un probléme du millénaire.

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
un_homme
Membre Naturel
Messages: 89
Enregistré le: 06 Nov 2008, 18:54

J'aurais résolu un probléme du millénaire.

par un_homme » 22 Nov 2015, 08:59

Salut,

Le problème du sac à dos étant donné une suite d'entier soit S un entier.
La question existe-t-il un sous ensemble tel que la somme totale soit de S, est un problème NP-complet.

Le problème revient à : est-il composé d'un monôme non nul dans le corps à 2 éléments, on note le coefficient associé ?

On considère une suite d'entiers premiers impaires tels que et avec



On considère les matrices de tel que :
soit la base canonique alors :
la matrice permute la sous-base en un
la matrice permute la sous-base en
...

On calcule en effet tout matrice inversible de est tel que

On calcule
...
On calcule .

On nomme le groupe formé par les matrices alors


Or ssi

Donc

Je ne vois pas d'erreur et vous ?

Merci.



Avatar de l’utilisateur
Sake
Habitué(e)
Messages: 1392
Enregistré le: 17 Juil 2014, 21:32

par Sake » 22 Nov 2015, 10:52

Salut contrexemple,

Toujours là avec tes interventions tirées par les cheveux ? Va donc poster ta "solution" sur Vixra, les gens se feront un plaisir de te corriger.

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 11:07

par Doraki » 22 Nov 2015, 10:54

Si je prends {1;2;3;4} et S=5,
peux-tu me donner le coefficient de X^5 dans (1+yX)(1+yX²)(1+yX^3)(1+yX^4), et peux-tu me dire s'il est possible d'obtenir une somme de 5 en prenant un sous-ensemble de {1;2;3;4} ?

un_homme
Membre Naturel
Messages: 89
Enregistré le: 06 Nov 2008, 18:54

par un_homme » 22 Nov 2015, 11:12

Sake a écrit:Salut contrexemple,

Toujours là avec tes interventions tirées par les cheveux ? Va donc poster ta "solution" sur Vixra, les gens se feront un plaisir de te corriger.

Je suis nul en anglais, ceci expliquant cela.

un_homme
Membre Naturel
Messages: 89
Enregistré le: 06 Nov 2008, 18:54

par un_homme » 22 Nov 2015, 11:17

Doraki a écrit:Si je prends {1;2;3;4} et S=5,
peux-tu me donner le coefficient de X^5 dans (1+yX)(1+yX²)(1+yX^3)(1+yX^4), et peux-tu me dire s'il est possible d'obtenir une somme de 5 en prenant un sous-ensemble de {1;2;3;4} ?

Excellent, un contrexemple.
Il suffit de prendre F un polynôme primitif de Z_2 aléatoire et on prend a une racine :
alors F(a)=0 et R(X)=(1+a*X^A1)...(1+a^(2^(n-1))*X^An).
Et alors là cela marche, presque toujours, il suffit de changer F.
Si on a un monôme non nul alors c'est possible (le problème du sac à dos est résoluble), sinon ce n'est pas possible avec une probabilité qui diminue exponentiellement à chaque fois que l'on change F.

un_homme
Membre Naturel
Messages: 89
Enregistré le: 06 Nov 2008, 18:54

par un_homme » 22 Nov 2015, 13:39

Alors personne ne voit d'erreur ?

Carpate
Habitué(e)
Messages: 3930
Enregistré le: 05 Jan 2012, 18:05

par Carpate » 22 Nov 2015, 14:13

un_homme a écrit:Je suis nul en anglais, ceci expliquant cela.

Et pas très bon en orthographe "j'ai résolut"

un_homme
Membre Naturel
Messages: 89
Enregistré le: 06 Nov 2008, 18:54

par un_homme » 22 Nov 2015, 14:14

Oui, espérons que je sois meilleur en mathématiques.

un_homme
Membre Naturel
Messages: 89
Enregistré le: 06 Nov 2008, 18:54

par un_homme » 22 Nov 2015, 15:09

Quelqu'un pourrait m'aider à partager cette procédure sur Vixar, cela permettrait de repérer d'éventuelle erreur.

Merci.

un_homme
Membre Naturel
Messages: 89
Enregistré le: 06 Nov 2008, 18:54

par un_homme » 22 Nov 2015, 17:05


nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 16:35

par nodjim » 22 Nov 2015, 18:04

Propose sur ce site :
http://www.forum.math.ulg.ac.be/viewsection.html?SESSID=a463229fdb923f71b25fd11b815002f5
tu devrais avoir des réactions, étant donné que ta démo est très courte.

un_homme
Membre Naturel
Messages: 89
Enregistré le: 06 Nov 2008, 18:54

par un_homme » 22 Nov 2015, 18:18

Merci, mais on dirait que ce forum est nettement plus actif que celui du lien.

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 16:35

par nodjim » 22 Nov 2015, 18:29

Certes, mais il y a beaucoup de pros là bas, tu ne seras pas déçu. Propose ta solution sans trop parler de la portée.

un_homme
Membre Naturel
Messages: 89
Enregistré le: 06 Nov 2008, 18:54

par un_homme » 23 Nov 2015, 13:57

L'erreur vient de là, l'algèbre des matrices n'est pas intègre :
un_homme a écrit:Or ssi

Merci, pour tous.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 34 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite