$NP$-complétude de cut-max

Celmar2Ceaumar
Celmar2Ceaumar
dans Fondements et Logique
Bonjour,
je ne comprends pas la fin de la preuve.

En fait je comprends très bien la construction du graphe. Par contre je ne comprends pas en quoi une affectation valide d'une instance de NAE3SAT fournit une coupure dans le graphe. Ce graphe représente la formule et non l'affectation qui rend la formule satisfiable donc je ne vois pas trop comment c'est possible.
Ce que je veux dire c'est que le graphe représente toujours la formule. Il ne tient pas compte de l'affectation, il n'en dépend pas. En tout cas c'est comme ça qu'a été construit le graphe. Donc qu'importe l'affectation qu'on choisit, on y trouve toujours la même coupure.

Voyez-vous ce que je veux dire ?
Merci pour votre aide

PS. Je m'excuse d'avance j'ai aussi posté ce message dans l'onglet d'informatique. J'ignore où le sujet a le plus sa place.95192
95194

Réponses

  • serge burckel
    serge burckel
    En effet, certains points ne sont pas très bien précisés dans cette preuve.

    1) Il faut voir que les arêtes définissent un 2-coloriage du graphe par les couleurs Vrai et Faux. Deux sommets reliés par une arête ont des couleurs différentes comme les sommets $x$ et $\lnot x$.

    2) Pour la dernière partie : <<Inversement, toute coupure de $G$...>>. En fait, il devrait dire :
    <<Inversement, toute coupure de $G$ qui correspond à une valuation valide des variables aura au plus $(2m+n)$ arêtes...>>
  • christophe c
    christophe c
    @Serge il n'y a pas de valuation dans (2).

    @Celmar je ne vois pas ce qui te gêne ni ce que tu veux dire.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • serge burckel
    serge burckel
    Je n'ai ni le temps ni une irrésistible envie de me plonger dans cette preuve.
    Cependant, c'est en effet la dernière partie qui me semble aussi "floue".

    Pour répondre à Christophe, la valuation en (2) est implicite. Elle est donnée par la partition $V_1,V_2$.
    Si je devais faire une preuve de ce truc, je serais tenté de mettre suffisamment d'arêtes (genre le nombre de clauses $m$) entre chaque paire $x,\lnot x$ pour forcer leur séparation dans une coupure maximale. On peut aussi donner une valeur aux arêtes (c'est en général comme cela que le problème est posé) et chercher à rendre maximale la sommation des arêtes entre les $V_1,V_2$.

    J'en profite pour proposer une notion sur les graphes : le noyau inductif. C'est une sorte d'axiomatique avec des problèmes associés résolubles en temps polynomial et d'autres $NP$-Complets.

    https://arxiv.org/abs/0710.1551
    ikg.pdf 87.2K
  • christophe c
    christophe c
    Une remarque que je me suis faite dans le métro, c'est qu'on a des tas de langages du genre:

    1/ L est polynomial et même très simple.

    2/ La restriction de L aux mots injectifs est NP-complet.

    Je ne sais pas si on a "des preuves" que tout algorithme qui reconnait si un mot est injectif prend forcément $Kn^2$ opérations où $n$ est la longueur du mot?
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    Un mot étant une suite finie, j'appelle "mot injectif" les suites finies injectives (vues comme, ce qu'elles sont, des fonctions définies sur un entier)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 4

Nicky LarsonXavier Vargai requin +1 Invité