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.