An Alternative proof of SAT NP-Completeness

hal.structure.identifier	Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.author	Paschos, Vangelis
hal.structure.identifier	Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.author	Escoffier, Bruno HAL ID: 5124
dc.date.accessioned	2011-04-18T14:43:06Z
dc.date.available	2011-04-18T14:43:06Z
dc.date.issued	2004
dc.identifier.uri	https://basepub.dauphine.fr/handle/123456789/5998
dc.language.iso	en	en
dc.subject	NP-completeness
dc.subject	reductions
dc.subject	second order logic.
dc.subject.ddc	003	en
dc.title	An Alternative proof of SAT NP-Completeness
dc.type	Document de travail / Working paper
dc.description.abstracten	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.
dc.publisher.city	Paris	en
dc.identifier.citationpages	207-213
dc.relation.ispartofseriestitle	Annales du LAMSADE
dc.description.sponsorshipprivate	oui	en
dc.subject.ddclabel	Recherche opérationnelle	en
dc.description.ssrncandidate	non
dc.description.halcandidate	oui
dc.description.readership	recherche
dc.description.audience	International
dc.date.updated	2020-07-22T14:24:45Z
hal.author.function	aut
hal.author.function	aut

Related items