Proving completeness by logic
Escoffier, Bruno; Paschos, Vangelis (2005), Proving completeness by logic, International Journal of Computer Mathematics, 82, 2, p. 151-161. http://dx.doi.org/10.1080/00207160412331296625
TypeArticle accepté pour publication ou publié
Journal nameInternational Journal of Computer Mathematics
Taylor & Francis
MetadataShow full item record
Abstract (EN)We first give a proof of SAT's NP-completeness based upon a syntactic characterization of NP given by Fagin in 1974. We illustrate the central 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. This new proof is, in some sense, 'more constructive' than Cook's classical one, as we need only to show how an NP problem can be expressed in terms of a second-order logical formula. Next, inspired by Fagin's characterization, we propose a logical characterization for the class NP-optimization (NPO), i.e., the class of optimization problems, the decision versions of which are in NP. Based upon this new characterization, we demonstrate the Min-NPO-completeness of MIN WSAT under strict reductions.
Subjects / KeywordsSAT; Reduction; Min-NPO-completeness; NP-completeness; Completeness
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é