P
Peu commune
Problème 3-SAT
Le problème 3-SAT est un problème surtout utilisé pour démontrer que d'autres problèmes sont NP-difficiles. C'est l'un des 21 problèmes NP-complets de Karp. Il s'agit de la restriction du problème SAT aux formules qui sont des formes normales conjonctives avec…
Extrait raccourci de l'article Wikipédia, CC BY-SA 4.0.