Proving completeness by logic

Abstract

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.

Keywords:

• Completeness
• NP-completeness
• Min-NPO-completeness
• Reduction
• SAT