Show simple item record

dc.contributor.authorEscoffier, Bruno
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-03-17T15:36:36Z
dc.date.available2010-03-17T15:36:36Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3733
dc.language.isoenen
dc.subjectSATen
dc.subjectReductionen
dc.subjectMin-NPO-completenessen
dc.subjectNP-completenessen
dc.subjectCompletenessen
dc.subject.ddc003en
dc.titleProving completeness by logicen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameInternational Journal of Computer Mathematics
dc.relation.isversionofjnlvol82en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2005-02
dc.relation.isversionofjnlpages151-161en
dc.relation.isversionofdoihttp://dx.doi.org/10.1080/00207160412331296625en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherTaylor & Francisen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record