Problème P=NP résolu?

Bonjour,
Dans le problème 3-SAT,il y a 3 littéraux pour lesquels on effectue une opération "ou". Ces opérations "ou" se réunissent en regroupements auxquels on effectue une opération "et". Le problème consiste à chercher à l'aide d'un algorithme s'il est possible de satisfaire un résultat vrai pour une ou plusieurs combinaisons de variables. Ce problème est NP-Complet donc si le problème est P, le problème P=NP est résolu et P=NP.
Pour démontrer que le problème 3-SAT est P, nous allons voir les conditions qui empêchent la satisfaction du résultat.
Dans le cas d'une forme disjonctive,nous aurions:
f=(v(1) et non (v1)) ou (v(2) et non v(2)) ou (v(3) et non v(3)) avec v(n) les variables propositionnelles et f la fonction insatisfaisable.
La forme conjonctive est donnée par le logiciel de calcul formel (image ci-jointe).
On n'oublira pas de rayer les v(n) qui ne sont pas assez suffisamment présent et à simplifier l'expression en supprimant la redondance. En effet pour avoir une forme insatisfaisable, nous devons avoir toutes les combinaisons possibles de (v(1),v(2),v(3)). Nous éliminerons tous les v(n) qui ne satisfont pas la condition d'insatisfabilité.
Passons à l'algorithme:
Entrée:
regroupement[] (liste de regroupements des 3 littéraux comme v(1) ou v(2) ou v(3)
Initialisation:
i=0
tailleregroupements=0
tailleregroupements=taille(regroupement[])
compteur={0...0} de taille 3*tailleregroupements // Soit un compteur pour chaque littéral.
suppression=0
Début:
Supprimer les éléments présents plus de 2 fois dans regroupement[]
tailleregroupements=taille(regroupement[])
Tant Que Vrai
suppression=0
Pour i Allant de 1 à 3*tailleregroupements de 1 en 1:
compteur(i)=Nombre ("v(i)",regroupement())+Nombre("non v(i)",regroupement())-Nombre(("v(i)" et "non v(i)",regroupement())
//On compte le nombre de v(n)
Fin Pour
Pour i Allant de 1 à 3*tailleregroupements de 1 en 1:
Si compteur(i)<8 et taille(regroupement)!=0: // Soit 8,le nombre de combinaisons nécessaires.
Supprimer les regroupements contenant v(i) dans regroupement[]
suppression=1
Arrêter boucle
Fin Si
Fin Pour
Si suppression=0:
Arrêter boucle
Fin Si
Fin Tant Que
Si taille(regroupement[])=0:
Afficher "Le problème est satisfaisable."
Sinon:
Afficher "Le problème est insatisfaisable."
Fin Si
Fin du programme.
Je vous transmet mon algorithme python via un lien:ici.
Je l'ai testé, il fonctionne.
Je vous remercie pour vos commentaires et vous remercie d'avance pour vos commentaires sur la démonstration.71508

Réponses

  • Bonjour,
    Je ne sais pas si j'ai du retard mais le prix du millénaire est encore à remporter.Voir ici.
  • Je ne comprends pas ce que tu veux dire par "nous aurions P(n) = blabla" ? Déjà le côté droit de l'expression ne dépend pas de $n$, et il est clairement insatisfaisable, je ne vois donc pas ce que ça vient faire là.

    Ensuite, si ton algorithme passe par la forme normale disjonctive, ça ne marchera pas parce que la conversion "forme normale conjonctive" $\to$ "forme normale disjonctive" n'est a priori pas en temps polynomial. C'est d'ailleurs pour ça que la question de savoir si une formule donnée en forme normale disjonctive est une tautologie est un problème co-NP-complet.

    Ensuite, et pour finir, un programme seul assez obscur ne sera pas une preuve de quoi que ce soit: il te manque la preuve qu'il est correct, et qu'il termine en temps polynomial, ce que tu n'as fait pour aucun des deux algorithmes que tu présentes.
    Si un jour tu prouves $P=NP$ ou $P\neq NP$, il te faudra un peu plus de travail que deux lignes de code ;-) (dis-toi que si la preuve de P=NP était si simple, vu le nombre de personnes qui travaillent dessus, le temps depuis lequel ils travaillent dessus et l'argent qui est en jeu, quelqu'un l'aurait trouvée)
  • Bonjour,
    Le "nous aurions P(n)" signifie que pour avoir 3 littéraux dans la liste "regroupement[]", il faut avoir 3 groupes réunis par un opérateur "ou". S'il y a plus de 2 éléments réunis par les parenthèses dans les opérateurs "ou" ils n'auront pas d'impact sur les P(n) mais pas d'impact non plus sur l'autre forme car on n'en tiendra pas compte dans la forme développée, ce qui n'est pas empêché par l'algorithme. La conversion de forme se fait en temps polynomial car il s'agit d'une base de données fixe qui est d'ailleurs calquée sur ce que j'obtiens à partir du logiciel de calcul formel quelque soit le problème de 3-SAT. Il s'agit d'un algorithme de reconnaissance de littéraux et de regroupements. Quant au fait que P(n) la proposition soit insatisfaisable, cela est prévu car l'algorithme détecte l' insatisfaisabilté en affectant un bit à chaque condition d' insatisfaisabilité. J'ai modifié le sujet pour clarifier ma pensée et élargir mon programme à tous les cas possibles.
  • @bound quoi que je n'ai rien compris à la rédaction de ton algorithme écrit en pur charabia (procure toi un livre d'algorithmique élémentaire et prend exemple dessus pour la rédaction) je pense que ton algorithme consiste grosso modo à rechercher dans ton expression l'existence ou non d' un groupe de 8 triplet en les mêmes variables propositionelles différentes les unes des autres (exemple (A ou B ou C) et (non A ou B ou C ) etc...)
    toujours d'après moi çà ne nécessite pas un truc non polynomiale pour ce faire et l'existence d'un tel groupe serait (au point ou j'en suis dans mes réflexions) une condition nécessaire et suffisante d'insatisfiabilité de la chose dont il est question

    cordialement
    juanita B
  • Bonjour et merci pour votre réponse,
    Vous êtes en train de me réconforter pour ma démonstration sur P=NP (et j'en suis très fier)même si mon algorithme n'est pas très bien rédigé.
    Cependant,j'ai fait un algorithme en Python, qui lui est disponible et est rédigé sans bug.
    De plus, il détaille l'algorithme que j'ai fait en "charabia".
    Vous pouvez le tester et voir à quel point il fonctionne agréablement bien.
    Sinon, j'explique pourquoi je teste les combinaisons:
    Pour avoir une insatisfaisabilité, il faut avoir dans la forme disjonctive (v(n) et non(v(n)), ce qui en développant donne l'ensemble des combinaisons possibles (soit 8 pour le problème 3-sat). Si, dans la forme conjonctive du problème 3-sat, il y a un motif d' insatisfaisabilité, cela est suffisant à cause du "et" qui oblige la satisfaction de toutes les conditions pour la satisfaction du problème.
  • Moi je suis trés fier de créer des fusées interplanétaires avec trois bouts de ficelle et un bâton, mais le problème c'est que celles de ma fabrication n'ont qu'un rayon d'action de trois mètres cinquante.
  • pour ce qui est de tester l'algorithme en python la réponse est non: je suis loin d'être une geek
    je me suis peut être trompée dans mon raisonnement (mais je pense pas) en tout les cas il semblerait que l'on soit arrivé à la même conclusion
    si je ne me suis pas trompée les matheux qui fréquentent en nombre ce forum vont pas trainer à comprendre le pourquoi du comment
    et si çà suffit à montrer p=np (formulation un chouilla paradoxale) je suis sur que tu trouveras bien quelqun pour t'aider à toucher la forte somme
    je serais curieux de savoir comment tu tes débrouillé pour arrivé a cette conclusion
    pour le reste j'en sais pas plus
  • Bonjour,
    @Shah d'Ock
    Elle serait drôle, votre blague, si je pouvais être sûr que j'avais faux mais le problème, c'est que j'ai testé un algorithme en Python (un vrai langage de programmation) et il semble marcher. Et je suis sûr qu'il est en temps polynomial car je ne fais pas apparaître d'instructions exponentielle.
    Sinon, je vais vous expliquer comment vous pourriez l'utiliser simplement:
    J'ai créé un objet v pour les variables.
    Pour faire appel à v(n) vous écrivez v(n). Pour faire appel à non(v(n)), vous écrivez v(n).neg().
    Pour la première formule((v(a) ou v(b) ou non v(c)) par exemple), vous gardez les doubles crochets.
    Pour les formules suivantes, vous mettez en crochets,séparé par des virgules vos 3 variables. Ce triplet vous le mettez dans regroupement.append().(il y a 3 variables car il s'agit du problème 3-sat).
    Essayez de ne pas laisser de trous(par exemple v(5) et v(7) sans v(6)), ça pourrait faire boguer l'algorithme.
    Ainsi, l'algorithme aura un tableau (ou une liste) bi-dimensionnel qui permettra de faire apparaître la formule.
  • > Moi je suis trés fier de créer des fusées interplanétaires avec trois bouts de ficelle et un bâton, mais le problème c'est que celles de ma fabrication n'ont qu'un rayon d'action de trois mètres cinquante.

    Mais la seule chose qui compte, c'est l'endroit où c'qu'elle tombe.
  • Je ne vais certainement pas m'amuser à faire tourner tous les scripts python des zigotos qui pensent avoir prouvé que P=NP (ce serait sans doute un non moyen d'attraper un virus).
    Soit tu postes une preuve convaincate que ton algorithme est correct et s'effectue en temps polynomial (pour l'instant, plusieurs personnes te l'ont déjà dit, c'est du charabia), soit tu contactes directement l'Académie des Sciences.
  • Bonjour,
    Je vais vous résumer en quelques mots ma preuve(de façon intuitive):
    Pour que le problème soit insatisfaisable, il faut avoir l'ensemble des combinaisons de bits dans le problème
    Pour ce faire, nous allons supprimer les regroupements identiques, et supprimer les regroupements contenant une variable dont le nombre n'est pas présent au moins 8 fois(le nombre de combinaisons possibles) dans l'ensemble du problème.
    Quant à votre question sur les virus:
    -Si j'étais un hacker, je ne m'amuserais pas à mettre le code source en ligne (via python)(histoire que l'on sache qu'il y a un virus(surtout dans un programme d'une cinquantaine de lignes)). Je préférerais un fichier exécutable.
    -Si cela peut vous rassurer, il existe des machines virtuelles (programmes qui isolent des applications du reste de la machine). Ainsi, si mon programme était un virus(ce qui n'est pas le cas), il ne s'attaquerait qu'à la machine virtuelle.
    -Il est également possible d’exécuter un programme sans risque sur un interpréteur en ligne puisque ce dernier ne donne pas accès aux fichiers de l'ordinateur.(fonctionnalité non disponible).Je vous envoie d'ailleurs un lien vers mon programme:ici
  • "Preuve" incompréhensible.
  • Bonjour,
    Vous me dites que vous ne comprenez rien à ce que j'ai écrit.
    Certes, je comprends que vous pensez que ce soit mal rédigé. Vous seriez aimable de me dire ce que vous n'avez pas compris. Ça me fera très plaisir de faire des éclaircissements y compris si cela doit être sur l'ensemble de ma preuve.
    Je ne saurais combien vous remercier même à l'avance.
    Ce qui est important à comprendre,c'est que dans une formule disjonctive(que l'on peut obtenir à partir de n'importe quelle forme conjonctive) pour qu'elle soit fausse,
    il faut que chacune des termes réunis par un opérateur "ou" soit faux. Dans ce groupement des termes réunis par un opérateur "ou", pour avoir plusieurs variables dont la réunion par la valeur "et" donne faux, quelque soit le résultat des autres variables,il faut que chacune des formes soit fausse.
    Or, si on prend un regroupement sans contradiction logique, le regroupement peut être satisfait à partir du moment que l'on remplace les non(v(n)) par v(n)=0 et les v(n) par v(n)=1.
    D'où la nécessité des contradictions logiques.
    En développant ces contradictions logiques, on obtient une combinaison de l'ensemble des bits pour le transformer dans la forme du problème des 3-SAT.
    D'où l'utilité de détecter cette combinaison en temps polynomial.
    Pour la détecter en temps polynomial, il faut simplifier la proposition, compter le nombre de v(n) dans la proposition, et supprimer chaque triplet qui contient un v(i) dont la quantité dans la proposition est inférieur à 8.
    Sinon je met le code en Python, pour ceux qui ont peur des virus et qui ne peuvent pas regarder:
    class v:
        def __init__(self,nombre):
            self.nombre=nombre
            self.signe=True        
        def neg(self):
            nouvelle_variable=v(self.nombre)
            nouvelle_variable.signe=not(self.signe)
            return nouvelle_variable
        def __eq__(self,other):
            if self.signe==other.signe and self.nombre==other.nombre:
                return True
            else:
                return False
        def __ne__(self,other):
            return not(self==other)
    
        def __lt__(self,other):
            if self.nombre<other.nombre or (self.signe==True and other.signe==False):
                return True
            else:
                return False
        def __le__(self,other):
            return (self==other or self<other)
    
        def __gt__(self,other):
            return (not (self<=other))
        def __ge__(self,other):
            return (not(self<other))
        def __repr__(self):
            non=""
            if self.signe==False:
                non="non "
            chaine=non + "v({0})".format(self.nombre)
            return chaine
    regroupement=[[v(1),v(2),v(3)]]
    regroupement.append([v(1),v(2),(v(3).neg())])
    regroupement.append([v(1),(v(2).neg()),v(3)])
    regroupement.append([v(1),(v(2).neg()),(v(3).neg())])
    regroupement.append([(v(1).neg()),v(2),v(3)])
    regroupement.append([(v(1).neg()),v(2),(v(3).neg())])
    regroupement.append([(v(1).neg()),(v(2).neg()),v(3)])
    regroupement.append([(v(1).neg()),(v(2).neg()),(v(3).neg())])
    regroupement.append([v(1),v(2),v(4).neg()])
    for element in regroupement:
        element.sort()
    elements_deux_fois=[x for x in regroupement if regroupement.count(x)>=2]
    elements_a_supprimer=[]
    for element in elements_deux_fois:
        if element not in elements_a_supprimer:
            elements_a_supprimer.append(element)
    for element in elements_a_supprimer:
        elements_deux_fois.remove(element)
    for element in elements_deux_fois:
        regroupement.remove(element)
    tailleregroupements_initial=len(regroupement)
    while True:
        tailleregroupements=len(regroupement)
        suppression=0
        compteur=[0]*(3*tailleregroupements_initial)
        for i in range(3*tailleregroupements_initial):
            for element in regroupement:
                if v(i+1) in element:
                    compteur[ i]+=1
                if (v(i+1).neg()) in element:
                    compteur[ i]+=1
                if v(i+1) in element and (v(i+1).neg()) in element:
                    compteur[ i]-=1
        for i in range(3*tailleregroupements_initial):
            if(compteur[ i]<8 and len(regroupement)!=0):
                for element in regroupement:
                    if v(i+1) in element or (v(i+1).neg()) in element:
                        regroupement.remove(element)
                        suppression=1
                        break
        if suppression==0:
            break
    if len(regroupement)==0:
        print("Probleme satisfaisable")
    else:
        print("Probleme insatisfaisable")
    
    Si vous voulez plus de détails sur le problème 3-SAT vous pouvez voir ici.
  • Bonsoir,

    j'ai appuyé sur "ça va ou quoi?" et ça ne marche pas.
    J'ai python version 6.0 pourtant.

    S
  • samok a écrit:
    Bonsoir,

    j'ai appuyé sur "ça va ou quoi?" et ça ne marche pas.
    J'ai python version 6.0 pourtant.
    Bonjour,
    Pour tester le programme Python, il faut la version 3 (et pas la version 6 qui n'existe pas).
  • Bon si je comprends bien tu passes de la forme normale conjonctive à la forme normale disjonctive. Ce qu'il est important de comprendre (et que Max t'a déjà expliqué), c'est que ça ne se fait (a priori) pas en temps polynomial.
    Si ton programme ne prend en entrée que des formes normales disjonctives, ben il ne résout pas 3-SAT.
  • Le passage de la forme normale conjonctive à la forme normale disjonctive en lui-même n'est pas dans l'algorithme. En effet, quand j'ai posté le sujet, j'avais une idée de comment résoudre le problème mais je ne savais pas comment généraliser et j'ai modifié l'algorithme dans le sujet depuis donc le commentaire de Max n'est plus d'actualité.
    Ce qui est dans l'algorithme, c'est la vérification de l'ensemble des motifs d'insatisfaisabilité(les 8 combinaisons que vous pouvez voir dans la capture d'écran Maple) que j'ai obtenu en temps exponentiel en dehors de l'algorithme, en comptant le nombre de même variables(que ce soit par exemple à la fois v(1) et non v(1)) dans la proposition.
    On pourrait penser que cela non plus ne se fait pas en temps polynomial sauf que je me suis rendu compte qu'il suffisait de simplifier la proposition et de compter le nombre de variables pour s'assurer qu'il y a toutes les combinaisons.
  • Oui ben désolé mais 3-SAT est défini par:
    Entrée: une forme normale conjonctive dont toutes les clauses ont au plus trois littéraux,
    Question: est-elle satisfaisable?
    Si ton algo ne prend pas en entrée des formes normales conjonctives, il ne répond pas à 3-SAT, point barre.
  • Bonjour,
    L'algorithme prend bel et bien, en entrée des formes normales conjonctives, l'opération de motifs d'insatisfaisabilité s'applique à une forme conjonctive sous forme de liste à 3 variables que je met dans l'algorithme pour donner le résultat.
  • Bon ben je ne comprends toujours pas comment est censé marcher ton algo alors.
  • Bonjour,
    S'il y a toutes les combinaisons possibles de variables, il y a 2^3=8 variables identiques. Il suffit de compter chacune des variables et s'il y en a moins de 8 on supprime tous les groupes de 3 littéraux qui contiennent cette variable, jusqu'à ce que les combinaisons pour les ensembles de triplets y soient toutes ou qu'il y en a aucune. En effet, comme je l'ai démontré avec mon logiciel de calcul formel,quand on développe l'expression insatisfaisable, on obtient toutes les combinaisons.
  • Comment procèdes-tu avec: $(v_1 \lor \neg v_2) \land (v_2 \lor \neg v_3) \land \dots \land (v_n \lor \neg v_{n+1}) \land (\neg v_1) \land v_{n+1}$?
  • Attends, une chose me tourmente... Tu ne crois tout de même pas que 3-SAT ça veut dire qu'on n'a le droit qu'à trois variables distinctes?
  • Bonjour,
    L'algorithme ne prévoit pas le cas avec 2 littéraux mais il est démontré par des chercheurs que le problème avec 2 littéraux est P voir ici.
  • Ben 3-SAT c'est des clauses d'au plus trois littéraux donc ton algo est censé pouvoir répondre à ma question.
    Tu n'as pas répondu à ma deuxième question.
  • Et c'est complètement évident, que 2-SAT est dans P. Mais ça n'était pas ma question.
  • Bon, vu que tu as l'air perdu dans une boucle infinie, on peut aussi remarquer que $(v_1 \lor \neg v_2) \land (v_2 \lor \neg v_3) \land \dots \land (v_n \lor \neg v_{n+1}) \land (\neg v_1) \land v_{n+1}$ est équivalente à $(v_1 \lor v_1 \lor \neg v_2) \land (v_2 \lor v_2 \lor \neg v_3) \land \dots \land (v_n \lor v_n \lor \neg v_{n+1}) \land (\neg v_1 \lor \neg v_1 \lor \neg v_1) \land (v_{n+1} \lor v_{n+1} \lor v_{n+1})$ dont toutes les clauses contiennent exactement trois littéraux.
  • Bonjour,
    Je ne suis pas dans une boucle infinie, c'est juste que le problème n'est pas forcément très simple à résoudre donc je réfléchis et je travaille pour la résolution du problème (en dehors de mes heures de cours auxquelles je participe en tant qu'étudiant dans un IUT(horaires très chargés et présence obligatoire pour valider le diplôme)).
    Donc on est d'accord que ce qui reste à démontrer c'est la possibilité de mélanger clauses à 3 littéraux et clauses à 2 littéraux.
    -Si l'un des deux problèmes: 2-SAT ou problème avec exactement 3 clauses (mon algorithme) ,est insatisfaisable, alors le problème associant les deux types de clauses est insatisfaisable du fait de l'opérateur "et", jusqu'ici tout paraît évident.
    -De même une proposition insatisfaisable "et logique" une proposition satisfaisable est insatisfaisable.
    -S'il y a une ou deux variables étrangères dans un groupe de 2 clauses par rapport aux groupes de 3 clauses, elle n'empêche pas la satisfaction d'une proposition(le développement en proposition conjonctive le montre).
    -S'il y en a dans plusieurs clauses, il suffit de regarder la satisfaisabilité séparément.
    -Sinon on peut factoriser la proposition satisfaisable P(3 clauses) dans chacun des cas(pour les clauses à 2 littéraux):
    (v(1) ou v(2)) et P = (v(1) et P) ou (v(2) et P) (satisfaisabilité non empêché,si P ne contient ni non(v(1)) ni non(v(2)),de même pour tous les cas avec une seule clause.
    v(1) et P(satisfaisabilité non empêché,si P ne contient pas v(1)),de même pour tous les cas avec une seule clause.
    (v(1) ou v(2)) et (v(1) ou non v(2)) et P = (v(1) et P) ou (v(1) et non v(2) et P) ou (v(2) et P) ou (v(2) et non v(2) et P)(satisfaisabilité non empêché si P ne contient pas non v(1)).
    (non(v(1)) ou non (v(2)) et (v(1) ou v(2)) et P = P (satisfaisabilité non empêché).
    (v(1) ou v(2)) et (v(1) ou non(v(2)) et (v(2) ou non v(2)=P et v(1) et v(2)(satisfaisabilité non empêchée si P contient ni non(v(1)),ni non(v(2)).
    Je suis quasiment sûr qu'il existe un algorithme permettant de finaliser tout ça en temps polynomial. Je vais essayer de le rédiger dès que je peux.
    Et merci pour vos conseils.
  • J'ai surtout l'impression que tu esquives les questions.
    J'ai modifié ma formule pour qu'elle soit acceptable par ton programme: ça ne devrait donc pas être bien compliqué de m'expliquer le déroulement de ton algo sur cette formule.
    Et tu n'as pas répondu à mon autre question: as-tu bien compris que 3-SAT ça veut dire trois littéraux par clause [et non l'inverse merci Gabu], mais qu'on peut utiliser autant de variables propositionnelles distinctes que l'on veut? Parce qu'il n'y a pas besoin d'être un génie pour s'apercevoir que des applications d'un ensemble de trois variables dans $\{0,1\}$, il y en a exactement $8$, et que de tester si l'une d'entre elle rend vraie une formule ne contenant que ces trois variables, ça se fait en temps linéaire.
  • Bonjour,
    J'ai compris que l'on peut utiliser n'importe quel type de variables (y compris triplets de 3 et couples de 2) c'est pour cela que je cherche comment avoir une proposition insatisfaisable avec des couples de 3 et de 2.
  • Non mais ça n'est PAS ma question. Tu as bien compris que tu dois pouvoir répondre à la satisfaisabilté de formules qui utilisent les variables X, Y, Z, T,... (et pas uniquement X,Y et Z)? Par exemple $(X \lor Y \lor \neg T) \land (X \lor T \lor \neg U) \land (\neg X \lor \neg Y \lor \neg T) \land (\neg X \lor Y \lor \neg T) \land (\neg X \lor \neg Y \lor T) \land (\neg Y \lor X \lor T) \land(\neg Y \lor X \lor \neg T)$.
  • Je relis ton message et je me dis que tu n'as pas compris ce que c'est qu'une variable. Parce que NON, une variable ça ne peut pas être un couple ou un triplet.
    Alors juste pour fixer le vocabulaire:
    Variable = symbole autre que $\land, \lor, \neg, (, )$,
    Littéral: variable éventuellement précédée du symbole $\neg$,
    Clause: suite de littéraux séparés les un des autres par le symbole $\lor$,
    Forme normale conjonctive: suite de clauses [et non de littéraux, merci Zomeu] entourées de parenthèses et séparées les unes des autres par le symbole $\land$.
    3-SAT: étant donnée une forme normale conjonctive dont toutes les clauses comportent au plus trois littéraux, existe-il une application de l'ensemble des variables dans $\{0,1\}$ qui la rende vraie?
  • @Shah d'Ock : si tu mélanges clauses et littéraux comme ici :
    "as-tu bien compris que 3-SAT ça veut dire trois clauses par littéraux"
    ou là :
    "Forme normale conjonctive: suite de littéraux entourés de parenthèses et séparés les un des autres par le symbole $\land$",
    ça ne va pas éclaircir cette mélasse !
    .
  • Bonjour,
    Je me suis mal exprimé mais je voulais dire ensemble de littéraux.(mais je me mélange les pinceaux).
    Pour la satisfaisabilité des formules bien sûr que j'ai compris qu'on peut utiliser plus de 3 variables d'où ma référence aux variables étrangères.
  • Ah oui merci Gabuzomeu effectivement je me suis embrouillaminé. Je corrige.
  • Bon c'est très bien que tu aies compris cela, maintenant vas-tu m'expliquer le déroulement de ton algo sur une des formules ci-dessus? Ca ne devrait pas être compliqué normalement, vu qu'il est déjà écrit, l'algo en question!
  • Bonjour,
    Je crois que j'avais raison depuis le départ dans le fait que mon algorithme prouve que P=NP et que j'ai perdu la certitude que c'était le cas car je ne savais rien du cas où il y a deux variables et j'ai donc donné des pistes de recherche à la place qui ne servent à rien.
    Revenons à notre forme disjonctive:
    Pour satisfaire l'insatisfasibilité,on a:
    f=(v(1) et non v(1) et v(2)) ou (v(2) et non v(2)) ou (v(3) et non v(3)) par exemple.
    Ce v(2) va se développer de manière à donner des groupes de 2 littéraux par exemple.
    Ainsi, on a la seule manière d'obtenir à la fois des clauses de trois littéraux et des clauses de deux littéraux de telle manière qu'ils soit insatisfaisables, qui est de rajouter des propositions dans les parenthèses de la forme disjonctive.
    Lors du développement, on obtient les motifs recherchés par mon algorithme.
    Cependant s'il y a une insatisfaisabilité lié à : (v(1) et non v(1)) ou (v(2) et non(v(2)), il ne sera détectable qu'avec un algorithme 2-SAT(qu'il faudra faire tourner en plus de mon algorithme pour résoudre le problème et que je ne suis pas sûr de pouvoir mettre sur internet car il est peut-être copyrighté.).
  • son algo d'après ce qu'il dit (je ne comprend pas le python ) se contente de verifier s'il y a un octuplé de clause comprenant le même triplé de variable par exemple
    ($x,y,z$).
    c'est ce que j'appelerais le comment de l'algoritme
    il me semble qu'a un certain moment il avait commencé à expliquer en langage comprehensible le pourquoi mais que ca a tourné en eau de boudin sur la fin

    bonjour chez vous
    juanita

    bon le temps que je tapote mes conneries bound à frappé (c'est pas archi clair soit dit en passant)
    pour le problème de copyright tu na qu'a ralonger ta formule logique de manière hadock pour qu'il n'y ait que des triplés
  • Bon sang de bois mais tu ne sais pas répondre à une question?!
    Je veux que tu m'expliques pas à pas le déroulement de ton algorithme sur la formule
    $(v_1 \lor v_1 \lor \neg v_2) \land (v_2 \lor v_2 \lor \neg v_3) \land \dots \land (v_n \lor v_n \lor \neg v_{n+1}) \land (\neg v_1 \lor \neg v_1 \lor \neg v_1) \land (v_{n+1} \lor v_{n+1} \lor v_{n+1})$. À la fin, cette formule est satisfaisable, ou non?
    Milgram: si tu as bien compris l'algorithme alors il est bien clair:
    -qu'il s'exécute en temps polynomial,
    -qu'il ne résout pas 3-SAT.
    Le bonjour chez vous aussi.
  • Bonjour,
    Je vais vous expliquer le déroulement de mon algo pour lequel on ne peut pas faire plus simple pour un problème aussi compliqué:
    -Il supprime les clauses de 3 littéraux présents plus de deux fois.
    -Tant qu'il reste des éléments à supprimer dans la liste il compte le nombre de même littéral dans la proposition et supprime les variables présents moins de 8 fois(le nombre de combinaisons).
    -S'il reste aucun triplet le problème est satisfaisable. Sinon il n'est pas satisfaisable.
  • Bon. Visiblement, la comlunication n'est pas possible entre nous deux. Vu que tu dis avoir résolu P vs NP, tu dois être très intelligent, donc le problème doit venir de moi. J'arrête là.
  • j'ai tendance à penser que le probléme 3sat n'est pas np complet quoique on puisse lire ou entendre ici ou la
    j'ai trainé mon cul assez longtemps à l'université pour m'apercevoir que les profs était particulierement facétieux
    j'ai d'ailleurs conservé assez de paperasse pour prouver mes dires
    maintenant soi je me suis planté dans mon raisonement sur ce problème
    soi je suis aussis genial que donald Trump (ce qui m'étonnerait vu que résolument je ne suis pas climatosceptique )
    soi 3 sat n'est pas np-complet

    passe le bonjour à tes voisins de ma part aussi
  • Ah oui, on en est à ce point-là de la discussion.
  • Bon demain je vérifie mon raisonnement et s'il n'est pas vérolé je le posterai.
    En attendant bonsoir.
    Cordialement.
    juanita
  • Bonjour,
    Sinon, il suffit de m'envoyer le lien du raisonnement.
    Ce n'est pas grave s'il est vérolé, j'ouvrirai le document dans une sandbox. Il suffit de me l'envoyer par message privé.
    Sinon, je suis vraiment désolé d'avoir vexé Shah d'Ock à ce point.
    Non, je ne me considère pas comme plus intelligent que les autres, intelligence qui n'est même pas définie scientifiquement contrairement à ceux qui parlent de QI ou d'intelligence artificielle. ,Je reconnais juste des facilités que j'ai pour comprendre les mathématiques qui sont en complet décalage avec la rigueur mathématique dans la rédaction que je ne possède pas n'ayant même pas fait une seule année de licence de mathématiques ou de classe préparatoire aux grandes écoles ou d'autres études de mathématiques.
    Sinon, à partir de maintenant l'algorithme résout le problème y compris s'il y a 2 littéraux (ou même quatre ou plus du seul moment où il n'y a pas de trous pour les littéraux)
    Voici le code source de mon nouveau programme:
    class v:
        def __init__(self,nombre):
            self.nombre=nombre
            self.signe=True        
        def neg(self):
            nouvelle_variable=v(self.nombre)
            nouvelle_variable.signe=not(self.signe)
            return nouvelle_variable
        def __eq__(self,other):
            if self.signe==other.signe and self.nombre==other.nombre:
                return True
            else:
                return False
        def __ne__(self,other):
            return not(self==other)
    
        def __lt__(self,other):
            if self.nombre<other.nombre or (self.signe==True and other.signe==False):
                return True
            else:
                return False
        def __le__(self,other):
            return (self==other or self<other)
    
        def __gt__(self,other):
            return (not (self<=other))
        def __ge__(self,other):
            return (not(self<other))
        def __repr__(self):
            non=""
            if self.signe==False:
                non="non "
            chaine=non + "v({0})".format(self.nombre)
            return chaine
    def satisfaisabilite(regroupement,nombre):
      regroupement_d=[x for x in regroupement if len(x)==nombre]
      tailleregroupements_initial=len(regroupement_d)
      while True:
        suppression=0
        compteur=[0]*(nombre*tailleregroupements_initial)
        for i in range(nombre*tailleregroupements_initial):
            for element in regroupement_d:
                if v(i+1) in element:
                    compteur[ i]+=1
                if (v(i+1).neg()) in element:
                    compteur[ i]+=1
                if v(i+1) in element and (v(i+1).neg()) in element:
                    compteur[ i]-=1
        for i in range(nombre*tailleregroupements_initial):
            if(compteur[ i]<2**nombre and len(regroupement_d)!=0):
                for element in regroupement_d:
                    if v(i+1) in element or (v(i+1).neg()) in element:
                        regroupement_d.remove(element)
                        suppression=1
                        break
        if suppression==0:
            break
      if len(regroupement_d)==0:
        return True
      else:
        return False
    def satisfaisabilite_globale(regroupement):
      satisfiable=True
      nombre=0
      for element in regroupement:
        if len(element)>nombre:
          nombre=len(element)
      for i in range(1,nombre+1):
        satisfiable= satisfaisabilite(regroupement,i) and satisfiable
      return satisfiable
    #On supprime les éléments pas présents nombre fois.
      
    regroupement=[[v(1),v(2),v(3)]]
    regroupement.append([v(1),v(2),(v(3).neg())])
    regroupement.append([v(1),(v(2).neg()),v(3)])
    regroupement.append([v(1),(v(2).neg()),(v(3).neg())])
    regroupement.append([(v(1).neg()),v(2),v(3)])
    regroupement.append([(v(1).neg()),v(2),(v(3).neg())])
    regroupement.append([(v(1).neg()),(v(2).neg()),v(3)])
    regroupement.append([(v(1).neg()),(v(2).neg()),(v(3).neg())])
    #regroupement.append([v(1),v(2)])
    regroupement.append([v(1),(v(2).neg())])
    regroupement.append([(v(1).neg()),v(2)])
    regroupement.append([(v(1).neg()),(v(2).neg())])
    for element in regroupement:
        element.sort()
    elements_deux_fois=[x for x in regroupement if regroupement.count(x)>=2]
    elements_a_supprimer=[]
    for element in elements_deux_fois:
      if element not in elements_a_supprimer:
        elements_a_supprimer.append(element)
      for element in elements_a_supprimer:
        elements_n_fois.remove(element)
      for element in elements_deux_fois:
        regroupement.remove(element)
    for element1 in regroupement:
      for element2 in element1:
        nombre=element1.count(element2)
        if nombre>1:
          for i in range(nombre):
            element1.remove(element2)
    if(satisfaisabilite_globale(regroupement)):
      print("Le probleme est satisfaisable.")
    else:
      print("Le probleme est insatisfaisable.")
    
    
    J'ai modifié le message car j'avais fait un bug puis car les crochets [ i] ont été interprétés comme de l'italique par le forum.
    J'ai modifié le fichier sur l'interpréteur en ligne et sur le premier lien également.
  • J'ai modifié la donnée initiale en reprenant presque ce que Shah d'Ock avait proposé. J'ai aussi ajouté une instruction pour afficher la clause à satisfaire.
    #! /usr/bin/python
    # -*- coding: utf-8 -*-
    
    class v:
        def __init__(self,nombre):
            self.nombre=nombre
            self.signe=True        
        def neg(self):
            nouvelle_variable=v(self.nombre)
            nouvelle_variable.signe=not(self.signe)
            return nouvelle_variable
        def __eq__(self,other):
            if self.signe==other.signe and self.nombre==other.nombre:
                return True
            else:
                return False
        def __ne__(self,other):
            return not(self==other)
    
        def __lt__(self,other):
            if self.nombre<other.nombre or (self.signe==True and other.signe==False):
                return True
            else:
                return False
        def __le__(self,other):
            return (self==other or self<other)
    
        def __gt__(self,other):
            return (not (self<=other))
        def __ge__(self,other):
            return (not(self<other))
        def __repr__(self):
            non=""
            if self.signe==False:
                non="non "
            chaine=non + "v({0})".format(self.nombre)
            return chaine
    
    def satisfaisabilite(regroupement,nombre):
      regroupement_d=[x for x in regroupement if len(x)==nombre]
      tailleregroupements_initial=len(regroupement_d)
      while True:
        suppression=0
        compteur=[0]*(nombre*tailleregroupements_initial)
        for i in range(nombre*tailleregroupements_initial):
            for element in regroupement_d:
                if v(i+1) in element:
                    compteur[ i]+=1
                if (v(i+1).neg()) in element:
                    compteur[ i]+=1
                if v(i+1) in element and (v(i+1).neg()) in element:
                    compteur[ i]-=1
        for i in range(nombre*tailleregroupements_initial):
            if(compteur[ i]<2**nombre and len(regroupement_d)!=0):
                for element in regroupement_d:
                    if v(i+1) in element or (v(i+1).neg()) in element:
                        regroupement_d.remove(element)
                        suppression=1
                        break
        if suppression==0:
            break
      if len(regroupement_d)==0:
          return True
      else:
          return False
    
    def satisfaisabilite_globale(regroupement):
      satisfiable=True
      nombre=0
      for element in regroupement:
        if len(element)>nombre:
          nombre=len(element)
      for i in range(1,nombre+1):
        satisfiable= satisfaisabilite(regroupement,i) and satisfiable
      return satisfiable
    #On supprime les éléments pas présents nombre fois.
    
    regroupement=[[v(1),v(1),v(2).neg()]]
    regroupement.append([v(2),v(2),(v(3).neg())])
    regroupement.append([v(3),v(3),v(4).neg()])
    regroupement.append([(v(1).neg()),(v(1).neg()),v(1).neg()])
    regroupement.append([(v(4).neg()),(v(4).neg()),(v(4).neg())])
    
    print regroupement
    
    for element in regroupement:
        element.sort()
    elements_deux_fois=[x for x in regroupement if regroupement.count(x)>=2]
    elements_a_supprimer=[]
    for element in elements_deux_fois:
      if element not in elements_a_supprimer:
        elements_a_supprimer.append(element)
      for element in elements_a_supprimer:
        elements_n_fois.remove(element)
      for element in elements_deux_fois:
        regroupement.remove(element)
    for element1 in regroupement:
      for element2 in element1:
        nombre=element1.count(element2)
        if nombre>1:
          for i in range(nombre):
            element1.remove(element2)
    if(satisfaisabilite_globale(regroupement)):
      print("Le probleme est satisfaisable.")
    else:
      print("Le probleme est insatisfaisable.")
    
    Voici ce que donne l'exécution :
    $ python toto.py 
    [[v(1), v(1), non v(2)], [v(2), v(2), non v(3)], [v(3), v(3), non v(4)], [non v(1), non v(1), non v(1)], [non v(4), non v(4), non v(4)]]
    Le probleme est insatisfaisable.
    
    Pourtant, si tous les v(i) sont faux, l'assertion est vraie (il y a une négation dans chaque proposition). À vrai dire, il ne donne pas la bonne réponse si on prend comme définition de regroupement
    regroupement=[[v(1),v(1),v(2).neg()]]
    
    ou
    regroupement=[[v(1),v(2).neg(),v(1)]]
    
    ce qui pose un peu problème quand même.

    Bref, ce programme ne répond pas convenablement.
  • Bonjour, cela est dû au fait que la fonction remove ne peut pas retirer le dernier élément.
    Je ne le savais pas (désolé, je ne suis pas non plus un gourou en Python).
    J'ai vérifié en débuggant, c'était le non(v(4)),donc 1 liste ne contenant qu'un littéral qui pose problème.
    Voici donc le nouveau code:
    class v:
        def __init__(self,nombre):
            self.nombre=nombre
            self.signe=True        
        def neg(self):
            nouvelle_variable=v(self.nombre)
            nouvelle_variable.signe=not(self.signe)
            return nouvelle_variable
        def __eq__(self,other):
            if self.signe==other.signe and self.nombre==other.nombre:
                return True
            else:
                return False
        def __ne__(self,other):
            return not(self==other)
    
        def __lt__(self,other):
            if self.nombre<other.nombre or (self.signe==True and other.signe==False):
                return True
            else:
                return False
        def __le__(self,other):
            return (self==other or self<other)
    
        def __gt__(self,other):
            return (not (self<=other))
        def __ge__(self,other):
            return (not(self<other))
        def __repr__(self):
            non=""
            if self.signe==False:
                non="non "
            chaine=non + "v({0})".format(self.nombre)
            return chaine
    def satisfaisabilite(regroupement,nombre):
      regroupement_d=[x for x in regroupement if len(x)==nombre]
      tailleregroupements_initial=len(regroupement_d)
      while True:
        suppression=0
        compteur=[0]*(nombre*tailleregroupements_initial)
        for i in range(nombre*tailleregroupements_initial):
            for element in regroupement_d:
                if v(i+1) in element:
                    compteur[ i]+=1
                if (v(i+1).neg()) in element:
                    compteur[ i]+=1
        for i in range(nombre*tailleregroupements_initial):
            if(compteur[ i]<2**nombre and len(regroupement_d)!=0):
                for element in regroupement_d:
                    if v(i+1) in element or (v(i+1).neg()) in element:
                        regroupement_d.remove(element)
                        if nombre==1:
                            del regroupement_d
                            return True
                        suppression=1
                        break
        if suppression==0:
            break
      if len(regroupement_d)==0:
        return True
      else:
        return False
    def satisfaisabilite_globale(regroupement):
      satisfiable=True
      nombre=0
      for element in regroupement:
        if len(element)>nombre:
          nombre=len(element)  
      for element in regroupement:        
          for i in range(nombre*len(regroupement)):
              if v(i) in element and v(i).neg() in element:
                   regroupement.remove(element)
      for i in range(1,nombre+1):
        satisfiable= satisfaisabilite(regroupement,i) and satisfiable
      return satisfiable
    #On supprime les éléments pas présents nombre fois.
    regroupement=[[v(1),v(1),v(2).neg()]]
    regroupement.append([v(2),v(2),(v(3).neg())])
    regroupement.append([v(3),v(3),v(4).neg()])
    regroupement.append([(v(1).neg()),(v(1).neg()),v(1).neg()])
    regroupement.append([(v(4).neg()),(v(4).neg()),(v(4).neg())])
    regroupement.append([(v(1).neg()),(v(2).neg())])
    for element in regroupement:
        element.sort()
    elements_deux_fois=[x for x in regroupement if regroupement.count(x)>=2]
    elements_a_supprimer=[]
    for element in elements_deux_fois:
      if element not in elements_a_supprimer:
        elements_a_supprimer.append(element)
      for element in elements_a_supprimer:
        elements_n_fois.remove(element)
      for element in elements_deux_fois:
        regroupement.remove(element)
    for element1 in regroupement:
      for element2 in element1:
        nombre=element1.count(element2)
        if nombre>1:
          for i in range(nombre-1):
            element1.remove(element2)
    if(satisfaisabilite_globale(regroupement)):
      print("Le probleme est satisfaisable.")
    else:
      print("Le probleme est insatisfaisable.")
    
    71756
  • OK, problème suivant, celui qu'a soulevé Shah d'Ock. En modifiant la déclaration de regroupement ainsi :
    regroupement=[[v(1),v(1),v(2).neg()]]
    regroupement.append([v(2),v(2),(v(3).neg())])
    regroupement.append([v(3),v(3),v(4).neg()])
    regroupement.append([(v(1).neg()),(v(1).neg()),v(1).neg()])
    regroupement.append([v(4),v(4),v(4)])
    # regroupement.append([(v(1).neg()),(v(2).neg())])
    
    print regroupement
    
    l'exécution donne :
    $ python toto4.py
    [[v(1), v(1), non v(2)], [v(2), v(2), non v(3)], [v(3), v(3), non v(4)], [non v(1), non v(1), non v(1)], [v(4), v(4), v(4)]]
    Le probleme est satisfaisable.
    
    C'est un problème car la dernière clause impose de prendre v(4) vraie, la troisième clause impose alors v(3) vraie, la deuxième impose alors v(2) vraie, la première impose alors v(1) vraie, contredisant l'avant-dernière clause.
  • Bonjour,
    Je reviens sur ce sujet car je pense avoir découvert une piste de recherche.
    Le problème 3-SAT se réduit au problème 1-dans-3-3SAT(qui dépend du théorème de Schaefer et dont je n'ai pas tenu compte dans mes programmes) dans lequel il n'y a que des clauses avec 1 seul et unique littéral positif et donc que des clauses avec 2 ou 3 littéraux.
    Comme le montre ma capture Maple et mes recherches(en tant que non chercheur) sur le sujet, il semble qu'il suffit que les clauses à deux littéraux contiennent des littéraux annulant ceux des clauses à trois littéraux pour que la proposition soit insatisfaisable. Cela semble être une condition nécessaire car il n'y a pas(je pense) de simplification possible permettant d'obtenir une proposition insatisfaisable à cause du fait que les combinaisons comme {v(1) ou v(2);v(1) ou non v(2);non v(1) ou v(2);v(2) ou non v(1)} car il n'y a qu'un seul et unique littéral positif.77238
Connectez-vous ou Inscrivez-vous pour répondre.