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
TypeDocument de travail / Working paper
Series titleAnnales du LAMSADE
MetadataShow full item record
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 / KeywordsNP-completeness; reductions; second order logic.
Showing items related by title and author.
Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis (2005) Article accepté pour publication ou publié