Résolution de P=NP

Bound

Bonjour. Voici ci-joint ma démonstration qui dit que P=NP. J'espère qu'elle est juste.

Si vous avez des questions ou des remarques, je suis à votre disposition.

EtNonLesShills

a+b n'est pas egal a a OU B mais a a XOR b

Héhéhé

Penses-tu que si $P=NP$ pouvait se résoudre par une simple résolution de systèmes linéaires de niveau L1 alors personne ne l'aurait remarqué ?

EtNonLesShills

A noter que tu peux exprimer OR a partir de NAND et donc bel et bien te ramener a un système d'équation de Z/2Z mais il sera non linéaire, je suppose que cette piste a du être creusée de fond en comble vu que c'est la plus naturelle

Bound

EtNonLesShills a dit :

a+b n'est pas egal a a OU B mais a a XOR b

Là, je me base sur 1-in-3 SAT pas sur 3-SAT donc il y a une seule variable satisfaite par clause. Donc fais-la table de vérité dans le cas où il n'y a qu'une seule variable de vrai parmi chaque clause et dis-moi le résultat. Peut-être, je ne l'ai pas détaillé dans la démonstration mais le plus important est qu'il n'y a qu'une seule clause par variable. Pour la NP-Complétude, j'ai trouvé un lien dessus en Wikipédia en anglais : https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Exactly-1_3-satisfiability Peut-être qu'ils racontent des choses fausses, je n'en sais rien.

PS: Je viens de modifier mon fichier PDF qui n'était pas clair là-dessus.

EtNonLesShills

Le xor de 3 variables a,b,c n'est pas egal a a xor b xor c par exemple (1,1,1) est faux pour xor(a,b,c) mais vrai pour a xor b xor c

Edited

Bound

EtNonLesShills a dit :

Le xor de 3 variables a,b,c n'est pas egal a a xor b xor c par exemple (1,1,1) est faux pour xor(a,b,c) mais vrai pour a xor b xor c

Edited

Le xor est vrai pour un nombre impair de variables, certes mais (1,1,1) ne correspond pas à 1-in-3-sat car on veut exactement 1 variable vraie par clausealors que (1,1,1) correspond à 3 variables vraies.

Heuristique

@EtNonLesShills L'erreur n'est pas dans les XOR, c'est un poil plus subtil.

@Bound Le problème de ton document vient du fait que tu confonds polynôme et fonction polynomiale. Considérons le polynôme $P(X) = X(1-X)$ sur le corps $\mathbb{F}_2$ (autrement dit $\{0,1\}$ comme tu le fais). Le polynôme $P$ vaut $X-X^2$ donc est non nul en tant que polynôme. Pourtant, $\forall x \in \{0,1\}, P(x) = 0$ donc la fonction polynomiale associée à $P$ est nulle. Ainsi, tu pourrais très bien avoir un polynôme non nul (dans ce cas, ton algo renvoie "Non satisfaisable") mais, pourtant, la fonction polynomiale est nulle, ce que tu ne pourras pas détecter.

Je t'invite à considérer ton système et ton polynôme pour l'unique clause $x \vee y \vee z$ pour comprendre le problème.

EtNonLesShills

Bound a dit :

EtNonLesShills a dit :

Le xor de 3 variables a,b,c n'est pas egal a a xor b xor c par exemple (1,1,1) est faux pour xor(a,b,c) mais vrai pour a xor b xor c

Edited

car on veut exactement 1 variable vraie par clausealors que (1,1,1) correspond à 3 variables vraies.

Bah justement je cite ton texte, tu dis qu'avoir une variable de vraie parmis (a,b,c) c'est equivalent a a+b+c =1
Non ca ne l'est pas comme je viens de te le montrer.

Heuristique

Pour le coup, il a raison sur ce point, il existe une unique variable vraie dans $\{a,b,c\}$ ssi $a+b+c = 1$. Dans ton exemple avec $(1,1,1)$, $a+b+c \neq 1$ et il n'y a pas unicité de la variable vraie. Ton souci vient du fait que l'auteur ne considère pas 3-SAT mais une variante. Mais rassurons-nous, sa preuve est tout de même fausse (le contraire aurait étonné tout le monde).

EtNonLesShills

Heuristique a dit :

il existe une unique variable vraie dans $\{a,b,c\}$ ssi $a+b+c = 1$. 

Pardon ? Bah non c'est faux

edit: je viens de comprendre ou est la malentendu, tu penses que l'auteur pars d'une instance verifiant 1 3 sat mais ca n'aurait aucun sens (moi aussi je peux construire un programme prenant en entre une instance  solvable dans 1 3 SAT et repondre a la question de savoir si elle solvable, je peux meme le faire en temps constant), non il part d'une instance quelquonque ne verifiant pas necessairement la condition d'existence. Enfin c'est la seule explication que j'ai trouve pour faire sens a ce que tu me dis.

L'auteur affirme ceci il existe une unique variable vraie dans $\{a,b,c\}$ ssi $a+b+c = 1$ sans aucune autre hypothèse sur (a,b,c)

Bound

Heuristique a dit :

@EtNonLesShills L'erreur n'est pas dans les XOR, c'est un poil plus subtil.

@Bound Le problème de ton document vient du fait que tu confonds polynôme et fonction polynomiale. Considérons le polynôme $P(X) = X(1-X)$ sur le corps $\mathbb{F}_2$ (autrement dit $\{0,1\}$ comme tu le fais). Le polynôme $P$ vaut $X-X^2$ donc est non nul en tant que polynôme. Pourtant, $\forall x \in \{0,1\}, P(x) = 0$ donc la fonction polynomiale associée à $P$ est nulle. Ainsi, tu pourrais très bien avoir un polynôme non nul (dans ce cas, ton algo renvoie "Non satisfaisable") mais, pourtant, la fonction polynomiale est nulle, ce que tu ne pourras pas détecter.

Je t'invite à considérer ton système et ton polynôme pour l'unique clause $x \vee y \vee z$ pour comprendre le problème.

Je ne confonds pas polynôme et fonction polynomiale car mes polynômes sont réels. C'est pour cette raison qu'il faut vérifier que X(X-1)=0 pour que X=0 ou X=1. J'ai modifié le PDF pour plus de clarté. Pour la clause "x ou y ou z", cela donne x=1-y-z donc ((1-x-y-z)(1-x-y-z-1))^2 qui est non nul donc cette fonction est satisfaisable.

PS: Il y a bel et bien une erreur dans ma démonstration que j'ai corrigée. Il faut bien vérifier que tous les coefficients soient nuls et pas que certains soient nuls.

Bound

Je vous ajoute le code de mon algorithme en Sagemath pour que vous puissier le tester sur votre ordinateur.

Je veux le million de dollars.

nombre_de_variables=3
liste_variables=[]
for i in range(nombre_de_variables):
    var("x"+str((i+1)))
    liste_variables.append("x"+str((i+1)))
#En dessous, on remplit les variables comme dans un solveur SAT
formule_a_satisfaire=[[1,2,-3],[1,2,3],[1,-2,3],[1,-2,-3]]
systeme_a_resoudre=[]
for i,clause in enumerate(formule_a_satisfaire):
    equation=0
    for j,variable in enumerate(clause):
        if int(variable)>0:
            exec("equation+=x{}".format(abs(int(variable))))
        else:
            exec("equation+=1-x{}".format(abs(int(variable))))
    systeme_a_resoudre.append(equation==1)
systeme_resolu=solve(systeme_a_resoudre,[ eval(i) for i in liste_variables])
if systeme_resolu==[]:
    raise Exception("Le système est insatisfaisable")
liste_variables_systeme_a_sommer=[]
for i,equation in enumerate(systeme_resolu[0]):
    liste_variables_systeme_a_sommer.append((equation.rhs()*(equation.rhs()-1))^2)
somme=simplify(expand(sum(liste_variables_systeme_a_sommer)))
if somme==0:
    print("Le système est satisfaisable")
else:
    print("Le système n'est pas satisfaisable")

Karnaj

Essaie avec [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]].

Bound

Effectivement, comme tu l'as remarqué,il y a une erreur de programmation qui ne correspond pas à ce que j'ai écrit dans mon papier. Il faut bel et bien que la somme vaille 0 pour que le problème soit satisfaisable. Je change ça tout de suite.

Karnaj

Essaie avec [1, 2, 3].

Heuristique

@EtNonLesShills Non, je ne pars pas du principe que l'auteur part d'une instance vérifiant le problème. La clause $a \vee b \vee c$ est correcte pour le problème ssi il existe un unique élément de $\{a,b,c\}$ valant $1$, ie $a+b+c = 1$.

Encore une fois, le problème ne vient pas de son système qui est correct (et qui est un problème équivalent), le problème vient du critère résultant sur le polynôme $P$.

Bound

Je m'avoue vaincu. Ma piste de recherche n'était pas la bonne et je me suis trop précipité à la publier. Merci pour ton retour Heuristique. Toutefois, j'ai une autre piste dont je parlerai une autre fois.

Karnaj

Est-ce que tu as déjà regardé ce qui se fait de ce côté de la recherche. C'est une bonne première étape pour voir ce qui a déjà été testé, les pistes qui ne semblent mener à rien ou qui semblent prometteuses, etc. J'aurais envie de dire que toute preuve/algo de moins de 2 pages (et c'est gentil) qui n'exploite pas de nouvelles idées est fausse. Et pour avoir de nouvelles idées, ou exploiter celles qui existent déjà, il faut déjà connaître celles qui existent déjà. Par exemple, des gens se sont déjà penchés sur de la résolution de problèmes comme SAT (et ses variantes) à base de système sans rien trouver de concluant.

Bibix

Pour le coup, il suffirait de penser à un nouveau problème $NP$-complet pour prouver $P = NP$ donc même une preuve d'une page me paraitrait crédible dans ce cas là (la difficulté se cachant derrière le fait de trouver le "bon" problème). C'est vraiment le seul problème du millénaire qui est dans ce cas là. J'attends avec impatience sa résolution par un lycéen.

Heuristique

Sachant que, comme nous avons plutôt en tête $P \neq NP$, cela devient beaucoup plus dur à faire pour un lycéen.

Karnaj

Et même en pensant à un nouveau problème NP-complet, il faudrait présenter le problème, montrer qu'il est NP-complet, donner l'algo de résolution et seulement là, faire sa preuve de correction et de complexité. Et si un tel problème permettait une preuve facile, alors ce nouveau problème serait en soi une grosse nouveauté !

EtNonLesShills

(je tiens a dire que meme apres avoir dormis et contempler 10 min le passage sur les polynome j'ai toujours pas compris ce que l'auteur voulait dire )

DISCLAIMER: toutes les variables booleenes sont considerees comme element de Z/2Z

juste par curiosité: ce qu'on peut faire c'est considerer le système linéaire de l'auteur sur les problèmes 1-3 sat. Pour tout $(x_{i,j} )_{(i,j) \in [0;n]^2}$ variables booleenes on a alors :   $(x_{i,j} )$ solution du probleme 1-3 sat  $\Rightarrow (x_{i,j} )$ solution du système linéaire associé considéré (heuristique si tu me dis qu'il ya équivalence encore une fois je hurle)

ca réduit alors les solutions a tester a card( ker (système linéaire)). On se limite aux problèmes nombre de variable = nombre de clause (donnant donc une matrice carrée comme système linéaire associé) et la intuitivement j'aurais dit que  pour tout k la probabilité en prenant un système linéaire au hasard que:
card (ker (système linéaire)) = $2^k$  c'est a peu près $2^{-(k+1)}$ ce qui donne une complexité en moyenne polynomiale ('mais juste en moyenne dommage pour le million) en brute forçant a tester si une des solutions du système est solution du problème 1-3 sat. Bon je suppose c'est faux, mais pourquoi ?

edit:  j'arrive pas a taper en latex ca me fait perdre le fil de mes pensées

Karnaj

Tu as une manière très simple si tu veux montrer à Heuristique qu'il a tort : trouver un contre-exemple, c'est-à-dire un triplet $(x, y, z)$ tel que $x + y + z = 1$ mais où la clause associée n'est pas satisfaite. En pratique, je pense que ça va être dur d'en trouver un vu que je suis de son avis, mais j'ai l'impression que toi, tu dis que tu prends tes variables dans les réels alors qu'elles sont dans $\{0, 1\}$ vu qu'elles correspondent à des variables d'une instance du problème.

EtNonLesShills

Karnaj a dit :

Tu as une manière très simple si tu veux montrer à Heuristique qu'il a tort : trouver un contre-exemple, c'est-à-dire un triplet $(x, y, z)$ tel que $x + y + z = 1$ mais où la clause associée n'est pas satisfaite. En pratique, je pense que ça va être dur d'en trouver un vu que je suis de son avis, mais j'ai l'impression que toi, tu dis que tu prends tes variables dans les réels alors qu'elles sont dans $\{0, 1\}$ vu qu'elles correspondent à des variables d'une instance du problème.

je l'ai déjà fait avec (1,1,1) mais le problème vient du fait qu'on considère deux affirmations différentes.

moi je considère:

pour tout (a,b,c) variable booléenne: (a ou b ou c) et non( plus d'une variable est vraie) <=> a+b+c =1, cette équivalence est fausse car avec (a,b,c) = (1,1,1) on aurait alors  1+1+1 =1 => (1 ou 1 ou 1) et non( plus d'une variable est vraie) vraie
soit vrai => faux qui est faux

alors qu'heuristique considère l'assertion suivante je crois:

pour tout (a,b,c) variable booléenne tel que une seule variable est vraie:  (a ou b ou c) et non( plus d'une variable est vraie) <=> a+b+c =1 qui pour le coup est vrai

sauf que comme l'auteur n'écrit pas de manière formelle quand il dit "...ce qui équivaut au système d'équation suivante..."

heuristique comprend le deuxième truc alors que moi le premier, par contre comme moi je l'écris dans mon dernier post ya pas de place au doute c'est le premier

edited: en fait je sais même pas ce qu'heuristique considère 

Heuristique

@EtNonLesShills Je te dis qu'il y a équivalence encore une fois, d'une part car c'est vrai, d'autre part pour te voir hurler.

Soient $a,b,c \in \{0,1\}$ (et je ne suppose rien de plus sur $a,b,c$).

Alors il existe un unique élément de $[a,b,c]$ valant $1$ ssi $a+b+c = 1$.

Dans ton exemple où $(a,b,c,) = (1,1,1)$ : 

1) il n'y a pas unicité d'un élément de $[a,b,c]$ valant $1$ (car il y en a 3) donc la proposition à gauche de l'équivalence est fausse.

2) $a+b+c = 3 \neq 1$ donc la proposition à droite de l'équivalence est fausse.

Ta proposition n'est donc pas un contre-exemple à mon équivalence.

Pour ta question sur le système, le cœur du sujet est justement qu'il n'est pas linéaire et que les variables sont prises dans le sous-ensemble $\{0,1\}$ de $\mathbb{R} : c'est ça qui rend le problème dur. 

EtNonLesShills

woa je croyais devenir fou j'ai enfin compris le malentendu tu travailles sur Z et moi sur Z/2Z et dans mon dernier post j ai tape R au lieu de Z/2Z ce qui a rajoute a la confusion, c est juste tellement naturel que dans ce cadre on se place dans Z/2Z pour moi

Heuristique

Oui, mon post pour l'auteur où je parle de $\mathbb{F}_2$ n'a sûrement pas aidé...

EtNonLesShills

Sinon concernant mon post de 15h31 ou est l erreur ? Dans la probabilité portant sur le card du noyau surement mais ca a l air tellement vrai intuitivement, je ferrais un programme pour tester si personne ne connait la réponse

Heuristique

Comme dit, le système de l'auteur du fil n'est pas linéaire du fait des contraintes $X(1-X) = 0$. On ne peut donc appliquer aucun résultat d'algèbre linéaire. Et, en général, cela m'étonnerait beaucoup que l'on ait une complexité polynomiale en moyenne pour un problème $NP$-complet sinon l'algo serait déjà implanté depuis belle lurette !

EtNonLesShills

Heuristique a dit :

Comme dit, le système de l'auteur du fil n'est pas linéaire du fait des contraintes $X(1-X) = 0$. On ne peut donc appliquer aucun résultat d'algèbre linéaire. Et, en général, cela m'étonnerait beaucoup que l'on ait une complexité polynomiale en moyenne pour un problème $NP$-complet sinon l'algo serait déjà implanté depuis belle lurette !

Quand je dis système associé je parle du système linéaire qu' il associe a une instance de 1 3 sat quand il dit en intro alors c est equivalent a blablabla mais avec coefficients dans Z/2Z, c est bien un système linéaire ? Sinon ca ne s applique que pour nombre de clause = nb de variables, et même si ce problème avec cette contrainte venait a être np complet je suis pas sur du tout que ca implique que tout les problèmes np complet aient un temps moyen polynomial, 3 sat en particulier, ca serait juste pour lui.

Heuristique

Le système doit justement être à coefficients dans $\mathbb{R}$ pour être correct, pour la fameuse condition $a+b+c = 1$. La différence avec un système linéaire classique est que l'on souhaite trouver des solutions dans $\{0,1\}$ et pas dans $\mathbb{R}$, ce qui complique énormément le problème. Rappelons qu'il est notamment $NP$-complet de savoir de savoir si un système linéaire à coefficients dans $\mathbb{N}$ admet une solution dans $\mathbb{N}$.

Pour ta question sur l'implication d'un tel algo polynomial en moyenne, les problèmes $NP$-complets ont pour caractéristique principale que tout problème de $NP$ peut se réduire à eux en temps polynomial. Ainsi, si tu prends une instance $x$ d'un problème $NP$ quelconque (appelons ce problème $L$), tu peux commencer par calculer en temps polynomial une instance $f(x)$ de $3SAT$ telle que $x \in L$ ssi $f(x) \in 3SAT$. On lance maintenant ton algo miracle de complexité moyenne polynomiale sur $f(x)$ et on a décidé en temps moyen polynomial si $x \in L$.

EtNonLesShills

Pour la première partie de ton message mais j'ai jamais parler de système correcte, de système équivalent au probleme1-3 sat, j'ai parle de système associe a un problème 1-3 sat, oui je suis au courant que ya pas équivalence entre le système possède des solutions et le problème lie en possède (j'ai même dis que je hurlerai si tu prétendais le contraire), par contre ya implication SI solution du probleme1-3 sat ALORS solution du système linéaire associe, ca permet de réduire les solution a tester.

J'ai pas fait d'étude d'info théorique mais la deuxième partie de ton message est fausse, déjà ya plein de problème np complet facile en moyenne cela vient du fait que la fonction f n'a pas forcement le bon gout d'être injective, f(x) pouvant avoir (et elle l'aura) la fâcheuse tendance a n'atteindre quasiment que les qq instances dures a décider. De plus j'ai bien specifié que cet algo ne marchait pas sur 1-3 sat mais une version bien plus simple (nombre de clause egales nombre de variables)

Bon je suis tente de m'arrete la vu que t'arrêtes pas de me faire dire des choses contraires a ce que j'ai dis et que de toute manière si ce programme marche, qqchose de similaire a sans aucun doute déjà été très vite découvert quand des gens se sont intéressés a 1-3 sat.

Heuristique

As-tu des exemples de problèmes $NP$-complets faciles en moyenne ? Si c'est le cas, ils le sont tous, à réduction polynomiale près.

EtNonLesShills

 Si c'est le cas, ils le sont tous, à réduction polynomiale près

 NOOOOON

Heuristique est ce que tu lis ce que j'ecris ? oui yen a plein, mais pour forcer le trait t'as juste a prendre un probleme ou pour tout n pour tout entre de taille n la sortie est 0 en temps lineaire mais pour l'instance restante la calculabilite est super dure.

T'as ca aussi sinon; https://interstices.info/idee-recue-si-un-probleme-est-np-complet-alors-ce-nest-pas-la-peine-de-sy-attaquer/ , ca fait très longtemps que j'ai pas fait de théorie des graphe et j'en ai fait très peu mais je suppose que l'auteur sait de quoi il parle.

Je te l'ai dit la réduction polynomiale ne préserve pas la complexité moyenne car toute les entrées peuvent être envoyées par ton f sur des entrées super difficile a décidées (qui peuvent existée car c'est en moyenne polynomial pas polynomial dans le pire cas)

Si tu veux une reduction polymomiale qui preserve la complexite moyenne deja il faudrait f injective, est ce suffisant ? mhh je dirais oui comme ca mais vraiment pas certain faudrait faire les maths pour voir

Bound

Bonjour. Voyant que ma méthode n'a pas fonctionné. J'ai décidé d'en essayer une nouvelle. J'ai décidé de transformer les problèmes 3-SAT en problèmes 2-SAT et j'espère que cette fois, j'ai vraiment résolu P=NP. Et encore merci beaucoup pour vos retours, cela me permet de progresser.

lourrran

En terme de complexité, on peut considérer que cette question P=NP, elle est assez comparable à la démonstration du théorème de Fermat. Est-ce plus complexe ou moins complexe, je n'en sais rien, mais c'est du très haut niveau, c'est un thème qui intéresse des cadors de très haut niveau, partout dans le monde. On parle des problèmes qui dépassent 99.99999% des mathématiciens.
Quand Wiles a publié sa démonstration en juin 1993, les relecteurs ont considéré qu'il manquait des pièces au puzzle.
Wiles s'est remis au travail, aidé par les relecteurs en question, et en septembre 1994, plus d'un an plus tard, il a proposé un nouveau document.
Plus d'un an pour corriger compléter la première version.

Toi, tu voles beaucoup plus haut que ces petits mathématiciens.
Une démonstration de P=NP.
Elle est fausse, il faut la refaire de A à Z ? 
Pas de problème, une semaine plus tard, tu as la nouvelle version. Ce n'est pas une évolution de la première, c'est une nouvelle démonstration, totalement différente.
Bravo, impressionnant.

Karnaj

Ce n'est pas parce que $\varphi$ est satisfiable et que $\psi$ est satisfiable que $\varphi \land \psi$ est satisfiable (prendre par exemple $\varphi = x$ et $\psi = \overline{x}$).

EDIT : la logique et la complexité sont des domaines élémentaires, mais pas simples, cela signifie notamment qu'il est très facile de faire une erreur quand on écrit une preuve, et les preuves nécessitent donc de prendre le temps de bien écrire les choses (c'est aussi le cas dans les autres domaines des maths me direz-vous). Tu ne quantifies pas tes variables, certaines affirmations (qui sont pourtant le cœur de ta preuve) ne sont pas justifiées, dur d'écrire une preuve (correcte) dans ce cas.

PS : vu que 2-SAT est dans NL, en fonction de l'algo que tu proposais (qui correspond à une réduction), on aurait presque pu te dire que t'es en train d'essayer de montrer que NL = NP...   

Heuristique

Bonsoir,

Au risque de répéter ce que beaucoup ont déjà dit, écrire "j'espère que cette fois, j'ai vraiment résolu $P = NP$" est au mieux naïf, au pire prétentieux. Des milliers de mathématiciens se sont penchés sur la question et avaient de très bonnes connaissances en complexité. Je doute qu'ils soient passés à côté d'une réduction d'à peine 2 pages de $3SAT$ à $2SAT$.

Ayant quelques bases de complexité, j'ai moi-même "démontré" une trentaine de fois $P = NP$ ou $P \neq NP$, comme de nombreux collègues chercheurs. Notre premier réflexe est alors de chercher la faute qui tombe souvent en 5 minutes. Si nous ne la trouvons pas, nous montrons notre "preuve" à un collègue pour trouver la faute car nous savons qu'il y a très peu de chances que le résultat se démontre facilement : et la "preuve" est contredite aussi vite qu'elle fut écrite. L'humilité devant tout ce travail voudrait que tu mâches 7 fois ton document avant de le publier, et que tu le fasses en nous demandant de t'aider à trouver où est la faute.

Préférant répondre aux auteurs de Shtam en exhibant l'erreur, je signale qu'il ne suffit pas de savoir si $A$ et $B$ sont satisfaisables. En effet, les variables qui apparaissent dans $A$ et $B$ sont les mêmes. Une valuation qui satisferait l'une pourrait contredire l'autre. Par exemple, si $a_i = y$ $A = x$ et $B = \neg x$, $A$ et $B$ sont toutes deux satisfaisables mais on ne peut écrire $(y \vee x) \wedge (\neg y \vee \neg x) = 1$.

De manière générale, tu confonds satisafaisable (il existe une valuation satisfaisant la formule) et valide (toute valuation satisfait la formule). Une formule valide peut être remplacée par $1$ car lui est sémantiquement équivalente mais certainement pas une formule satisfaisable. 

Bound

Bonjour Heuristique et Karnaj.

Merci de vos retours rapides et merci d'avoir pris le temps de me répondre.

@Heuristique C'est vrai que je suis prétentieux et désolé si tu l'as mal pris.

Il est vrai que n'ayant même pas une licence, je ferais mieux de me taire.

Je crois que je ferais mieux d'abandonner ce problème et de réviser pour mes examens car je suis ridicule.

PS: Je remercie les intervenants de ce forum pour votre gentillesse de faire ce travail gratuitement et bénévolement et je suis désolé de ne pas être à la hauteur.

Karnaj

Tu peux bien sûr continuer à travailler sur le problème, il faut juste avoir l'humilité de savoir qu'on ne va sans doute pas réussir à le résoudre. Tu apprendras des choses, et pourquoi se restreindre si ça te plaît de travailler sur ce sujet. La prétention n'est pas de travailler sur le sujet, mais de croire avoir résolu le problème. 

Comme Heuristique l'a dit, on trouve souvent des preuves (fausses) de P = NP. Et généralement, on le fait sans même faire exprès, en travaillant sur un autre projet. Ça m'est arrivé pas plus tard que la semaine dernière. Au début, je pensais avoir une preuve du résultat que je cherchais à montrer. Quand j'ai compris que ça revenait à montrer P = NP, je ne me suis pas dit que j'avais démontré P = NP, je me suis dit qu'il y avait sûrement une erreur dans ma preuve.

C'est ce point de vue que tu dois adopter. Tu penses avoir une idée d'algo et de preuve, tu les écris en détail en vérifiant chaque étape, et si besoin, tu demandes de l'aide pour trouver l'erreur. La plupart du temps, l'erreur sera grossière, mais parfois, elle sera dans les détails (une exponentielle cachée quelque part, etc.).

Bound

Bonjour. Merci Karmaj pour ton encouragement. Ce que je voulais dire dans ma démonstration - effectivement je n'ai pas quantifié mes variables donc ce n'était pas clair mais peut-être j'enverrai une meilleure rédaction (si elle existe bien sûr) lorsque j'aurai le temps - c'est que $F_i$ est satisfaisable si et seulement si A l'est ou B l'est, c'est ce qui "permettrait" à mon algorithme de fonctionner. En fait, je regarde localement pour chaque variable et je ne sélectionne que les clauses contenant cette variable. D'ailleurs, dans le cas que présente Heuristique, comme je regarde localement, en y : il y a une solution à la fois pour y=1 (y=1,x=0) et y=0 (y=0;x=1) et c'est ça que je voulais dire même si c'est clair comme du jus de boudin. 

Certes, la condition $F=\bigwedge_{i=1}^m F_i$ est satisfait si et seulement si $\forall i \in [1,M], F_i$ est satisfait mérite une preuve mais je me place dans le cas où on garde les clauses contenant le littéral et uniquement ceux-ci.

Effectivement, il y a moins d'une chance sur le nombre de Graham (pour ce qui ne connaisse pas la référence, c'était il y a une trentaine d'années le plus grand nombre qui était apparu dans une démonstration) que je résolve P=NP mais il ne faut  pas abandonner.

Heuristique

Comme le dit @Karnaj , il n'y a aucun problème pour proposer de nouvelles preuves de $P = NP$, du moment que tu le fais avec l'humilité nécessaire. Si tu veux augmenter ta probabilité de réussir à 2 sur le nombre de Graham, tu peux commencer par apprendre des trucs sur la complexité et la logique : cela te sera sûrement utile pour mieux comprendre le problème.

Je suis d'accord pour dire que $F_i$ est satisfaisable ssi $A$ est satisfaisable ou $B$ est satisfaisable. En revanche il est faux de dire que $\bigwedge\limits_{i = 1}^m F_i$ est satisfaisable ssi tous les $F_i$ le sont. Etant données 2 formules $\varphi$ et $\psi$ satisfaisables, on ne peut assurer que $\varphi \wedge \psi$ l'est encore. Il suffit pour cela de regarder $x \wedge \neg x$ pour s'en convaincre.

Voici un exemple plus proche de ton problème, tiré de $x \Leftrightarrow y \Leftrightarrow z \Leftrightarrow \neg x$ où tu m'accorderas la non satisfaisabilité.

Considérons $F = (\neg x \vee y) \wedge (x \vee \neg y) \wedge (\neg y \vee z) \wedge (y \vee \neg z) \wedge (\neg z \vee \neg x) \wedge (z \vee x)$. Tu pourras vérifier que cette formule est équivalente à la précédente et donc non satisfaisable. Toutefois :

$F_x = (\neg x \vee y) \wedge (x \vee \neg y) \wedge (\neg x \vee y) \wedge (x \vee \neg y)$ qui revient à $(x \Leftrightarrow y) \wedge (z \Leftrightarrow \neg x)$ qui est satisfait par $(x,y,z) = (1,1,0)$.

$F_y = (\neg x \vee y) \wedge (x \vee \neg y) \wedge (\neg y \vee z) \wedge (y \vee \neg z)$ qui revient à $(x \Leftrightarrow y) \wedge (y \Leftrightarrow z)$ qui est satisfait par $(x,y,z) = (1,1,1)$.

$F_z = (\neg y \vee z) \wedge (y \vee \neg z) \wedge (\neg z \vee \neg x) \wedge (z \vee x)$ qui revient à $(y \Leftrightarrow z) \wedge (z \Leftrightarrow \neg x)$ qui est satisfait par $(x,y,z) = (0,1,1)$.

Toute la difficulté de $SAT$ réside dans le fait que l'on ne peut pas regarder indépendamment chaque variable $x$ via $F_x$ car la valeur de $x$ a des conséquences qui ne sont pas juste locales (dans $F_x$) mais qui impactent toute la formule $F$.

Bound

Bonjour. Merci pour ton retour Heuristique et d'avoir pris le temps de me répondre. Tu as raison, ma démonstration ne marche pas. Je m'avoue de nouveau vaincu.

octobre

Vraiment je ne comprend pas pourquoi on cherche a démontrer que N=PN mathématiquement, cela ne dépend peut être pas d'algo, avec un oridnateur quantique avec beaucoups de Qbit tout problème PN devient un simple problème P 
Par exemple L'algorithme de Shor est une réalisation monumentale de l'informatique quantique, réputée pour sa capacité sans précédent à factoriser de grands nombres exponentiellement plus vite que n'importe quel algorithme classique.

Bibix

Bah oui et même sans parler d'informatique quantique, la résolution de certains problèmes NP-complet peut être parallélisée ce qui fait qu'on peut les résoudre en temps linéaire en prenant un nombre suffisant de processeurs en parallèle donc ce sont des problèmes P .

Math Coss

Je ne comprends pas : cela signifie que le nombre de processeurs doit augmenter avec la taille des données ? Pour un résultat asymptotique, ça va prendre beaucoup de place !

gerard0

Rappel : Les interventions d'Octobre sont toujours du genre "je n'y comprends rien mais ça ne m'empêche pas de parler".

Heuristique

@octobre Les classes de complexité quantique n'ont a priori rien à voir avec les classes de complexité quantique. Parler de $P = NP$ en quantique n'a donc pas de sens. Il existe des classes quantiques, comme $BQP$ qui permettent de capturer la complexité quantique. Aujourd'hui, on sait essentiellement que $P \subset BQP$ (on peut faire en temps polynomial quantique tout ce que l'on sait faire en temps polynomial classique).

Le problème de factorisation n'étant pas $NP$-dur (du moins, on ne l'a pas démontré), l'algorithme de Shor ne prouve absolument pas $NP \subset BQP$. Beaucoup pensent d'ailleurs que les problèmes $NP$-complets ne peuvent être résolus en quantique. Ajoutons enfin que l'on ne sait pas encore si $P = BQP$ et que l'on ne sait donc pas si le quantique a strictement plus de puissance que le classique (même si on y croit très fort). Il existe peut-être un algorithme classique de factorisation en temps polynomial : on pense que non, mais on peut être surpris.

@Bibix Il y a également des classes de complexité pour les algos en parallèle mais où le nombre de processeurs est borné par une fonction imposée : voir par exemple https://fr.wikipedia.org/wiki/NC_(complexité) . Notamment, pour la classe $NC$ indiquée, on a $NC \subset P$. Avec $2^n$ processeurs qui s'exécutent en temps linéaire, ce n'est pas vraiment ce que l'on appelle un temps polynomial...

octobre

@Heuristique
Merci pour votre réponse si par exemple on prouve que la factoisation du nombre est NP et que P=BQP est ce que dans ce cas P=NP ?
En clair si on arrive a résoudre un probleme NP avec un alghorithme quantique dans un temps polynomnial et on plus on arrive a prouvé que P=BQP dans ce cas P=NP...
@gerard0
Si je comprend ce problème on a plusieurs sorties et on cherche une entré clé pour que tout les sorties soit active.

123rourou

Si BQP (Bounded-Error Quantum Polynomial Time) signifie pour toi que c'est une classe de complexité qui permet la résolution par un ordinateur quantique en temps polynomial, alors RSA se fait en temps polynomial en gros. L'algorithme de Shor fonctionne en O((log⁡N)^2).

un article relativement recent  https://securite.developpez.com/actu/339998/-Comment-casser-le-RSA-avec-un-ordinateur-quantique-le-resultat-d-une-recherche-theorique-publie-par-un-groupe-de-chercheurs-chinois/

Par contre, il faut prendre cela avec des pincettes, parce que les ordinateurs quantiques, c'est comme la bombe c'est une histoire de k*k*te