Press "Enter" to skip to content

Problème SAT

le problème de satisfaction en logique* propositionnelle consiste à déterminer si une formule, exprimée en logique propositionnelle, est vraie ou fausse. Ce problème est très important en informatique, car il constitue la référence des problèmes difficiles à résoudre (ce qui est l’objet de la théorie de la complexité algorithmique*). Il sert de référence pour résoudre / étudier des problèmes qui lui sont réductibles ou auxquels il est réductible, tels que la vérification de logiciels, de micro-processeurs, ou de systèmes complexes.