An Alternative proof of SAT NP-Completeness

Paschos, Vangelis; Escoffier, Bruno

Paschos, Vangelis; Escoffier, Bruno (2004), An Alternative proof of SAT NP-Completeness. https://basepub.dauphine.fr/handle/123456789/5998

Voir/Ouvrir

AN2LAMSADE_207-213.pdf (166.3Kb)

Type

Document de travail / Working paper

Date

2004

Titre de la collection

Annales du LAMSADE

Ville d’édition

Paris

Pages

207-213

Métadonnées

Afficher la notice complète

Auteur(s)

Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Escoffier, Bruno
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]

Résumé (EN)

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.