Thumbnail

An Alternative proof of SAT NP-Completeness

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

View/Open
Type
Document de travail / Working paper
Date
2004
Series title
Annales du LAMSADE
Published in
Paris
Pages
207-213
Metadata
Show full item record
Author(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]
Abstract (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.
Subjects / Keywords
NP-completeness; reductions; second order logic.