Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorEscoffier, Bruno
dc.date.accessioned2011-04-18T14:43:06Z
dc.date.available2011-04-18T14:43:06Z
dc.date.issued2004
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5998
dc.language.isoenen
dc.subjectNP-completeness
dc.subjectreductions
dc.subjectsecond order logic.
dc.subject.ddc003en
dc.titleAn Alternative proof of SAT NP-Completeness
dc.typeDocument de travail / Working paper
dc.description.abstractenWe 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.
dc.publisher.cityParisen
dc.identifier.citationpages207-213
dc.relation.ispartofseriestitleAnnales du LAMSADE
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2020-07-22T14:24:45Z


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