Abstract FR:

Nous étudions les problèmes combinatoires NP-complets autour de la Satisfaisabilité (SAT) : 3-Colorabilité (3COL), Hamiltonicité (HAM), etc. , et les réductions fines entre ces problèmes et leurs versions planaires. Nous cherchons à préserver la structure des solutions (parcimonie), la complexité des problèmes (linéarité), et la géométrie des instances (planarité). Nous exhibons une réduction quadratique et parcimonieuse de 3COL à PLAN-3COL et une réduction linéaire, planaire, et parcimonieuse de SAT à 3COL, unifiant et rafinant les preuves de NP-complétude et de \#P-complétude pour 3COL, PLAN-3COL, \#3COL et \#PLAN-3COL, et montrant la DP-complétude de UNIQUE-3COL et UNIQUE-PLAN-3COL. Nous établissons l'équivalence linéaire et parcimonieuse de PLAN-SAT et de PLAN-HAM, un lien peu probable entre SAT et HAM. Nous exhibons enfin une formule Existentielle Monadique du Second Ordre prouvée minimale et unique, définissant un problème NP-complet sur structures bijectives.