Titre du document / Document title

Satisfiabilité de 1-parmi-3 planaire est NP-complet = Planar 1-in-3 satisfiability is NP-complete

Auteur(s) / Author(s)

LAROCHE P. ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

LITP, 75005 Paris, FRANCE

Résumé / Abstract

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

Revue / Journal Title

Comptes rendus de l'Académie des sciences. Série 1, Mathématique    ISSN  0764-4442   CODEN CASMEI 

Source / Source

1993, vol. 316, n^o4, pp. 389-392 (6 ref.)

Langue / Language

Français

Editeur / Publisher

Elsevier, Paris, FRANCE  (1984-2001) (Revue)

Mots-clés anglais / English Keywords

Planar graph

;

Algorithm

;

Logical function

;

NP complete problem

;

Satisfiability problem

;

Mots-clés français / French Keywords

Graphe planaire

;

Algorithme

;

Fonction logique

;

Problème NP complet

;

Formule booléenne

;

Formule planaire

;

Fonction 1 parmi 3

;

Problème satisfiabilité

;

Mots-clés espagnols / Spanish Keywords

Grafo planario

;

Algoritmo

;

Función lógica

;

Problema NP completo

;

Localisation / Location

INIST-CNRS, Cote INIST : 116 A, 35400003880029.0180