Détail de la notice
Titre du Document
Satisfiabilité de 1-parmi-3 planaire est NP-complet
Planar 1-in-3 satisfiability is NP-complete
Auteur(s)
LAROCHE P.
Résumé
Le problème de la satisfiabilité de formules booléennes, dans diverses formes normales, a été largement étudié. De nombreux types de restrictions, sur les clauses ou les variables, ont été proposés, qui conservent la NP-complétude du problème. Ainsi la satisfiabilité de formules de logique planaires est un problème qui reste NP-complet. Par ailleurs, Schaeffer a étudié les formules constituées de conjonctions de fonctions logiques quelconques à n variables. en particulier, la fonction 1-parmi-3 donne ainsi un problème NP-complet. Nous étudions ici l'application de ces deux restrictions simultanément
Editeur
Elsevier
Identifiant
ISSN : 0764-4442 CODEN : CASMEI
Source
Comptes rendus de l'Académie des sciences. Série 1, Mathématique A. 1993, vol. 316, n° 4, pp. 389-392 [bibl. : 6 ref.]
Langue
Français
Pour les membres de la communauté du CNRS, ce document est autorisé à la reproduction à titre gratuit.
Pour les membres des communautés hors CNRS, la reproduction de ce document à titre onéreux sera fournie sous réserve d’autorisation du Centre Français d’exploitation du droit de Copie.

Pour bénéficier de nos services (strictement destinés aux membres de la communauté CNRS (Centre National de la Recherche Scientifique), de l'ESR français (Enseignement Supérieur et Recherche), et du secteur public français & étranger) :