Date
2004
Ville de l'éditeur
Paris
Nom de l'éditeur
Université Paris-Dauphine
Titre de la collection
Annales du LAMSADE
n° dans la collection
2
Lien vers un document non conservé dans cette base
http://hal.archives-ouvertes.fr/hal-00017602/en/
Indexation documentaire
Recherche opérationnelle
Subject
NP-completeness; reductions; second order logic.
Auteur
Escoffier, Bruno
Paschos, Vangelis
Type
Document de travail / Working paper
Nombre de pages du document
207-213
Résumé en anglais
We give a proof of SAT's NP-completeness based upon a syntaxic characterization of NP given by Fagin at 1974. Then, we illustrate a part of our proof by giving examples of how two well-known problems, MAX INDEPENDENT SET and 3- COLORING, can be expressed in terms of CNF. Finally, in the same spirit we demonstrate the min NPO-completeness of MIN WSAT under strict reductions.
