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
199 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
 
 
 
 
 

$NP$-complétude de cut-max

Envoyé par Celmar2Ceaumar 
$NP$-complétude de cut-max
il y a deux mois
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.

[Doublon. Continuer sur l'autre discussion. AD] [www.les-mathematiques.net]



Edité 3 fois. La dernière correction date de il y a deux mois et a été effectuée par AD.


Désolé,vous ne pouvez pas répondre à cette discussion, elle est fermée.
Liste des forums - Statistiques du forum

Total
Discussions: 140 875, Messages: 1 378 564, Utilisateurs: 25 702.
Notre dernier utilisateur inscrit mouradammour.


Ce forum
Discussions: 2 382, Messages: 17 542.

 

 
©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