En logique mathématique, la satisfaisabilité ou satisfiabilité et la validité sont des concepts élémentaires de sémantique. Une formule est satisfaisable...

En informatique théorique, le problème SAT ou problème de satisfaisabilité booléenne est le problème de décision, qui, étant donné une formule de logique...

simples (en temps polynomial) à tester la satisfaisabilité de sa négation. Le problème de la satisfaisabilité d'une proposition, à savoir trouver une configuration...

\Box \psi )} On peut également définir les notions de validité, de satisfaisabilité et d'équivalence en se restreignant à un modèle, à un cadre ou à une...

importance en théorie de la complexité des algorithmes s'intéressant à la satisfaisabilité d'une formule logique. Sur les autres projets Wikimedia : Sat, sur...

logique polyvalente (à nombre fini de valeurs) est complète et que la satisfaisabilité est décidable. Une logique p-valente a p(pn) connecteurs n-aires pour...

conjecture est vraie, alors il est démontré que le problème NP-complet de k-satisfaisabilité, avec k ≥ 3 {\displaystyle k\geq 3} , ne peut être résolu par un algorithme...

ensembles récursivement énumérables (pour la réduction récursive). La satisfaisabilité d'un ensemble de clauses du calcul propositionnel est un problème NP-complet...

définitions : celles relatives à l'utilisation de modèles (du premier ordre) : satisfaisabilité et falsifiabilité, loi logique et contradiction logique, conséquence...

Cependant, la satisfaisabilité des propositions de MSO2 décidable pour les graphes de largeur arborescente bornée et de satisfaisabilité des propositions...

désigner un ensemble de méthodes visant à résoudre le problème de satisfaisabilité. Différents corpus mathématiques ont été utilisés pour élaborer des...

générer la clause vide. Par contre, le problème de la consistance (satisfaisabilité) n'étant pas décidable en logique des prédicats, il n'existe pas de...

effectivement dans le monde réel. Pour cela, Tarski introduit le concept de satisfaisabilité, au sens que la proposition "il neige" est satisfaite par la réalité...

proches mais plus "faciles" à résoudre. C'est notamment le cas de la satisfaisabilité d'une formule de Horn, puisqu'il s'agit d'un problème P-complet, plus...

manière probabiliste pour un problème NP-complet comme le problème de satisfaisabilité booléenne. Dans un système de preuves vérifiables de manière probabiliste...

des fonctions qui permettent de réaliser des tests de cohérence (ou satisfaisabilité) en temps polynomial en la taille du circuit, en contre-partie de tels...

théorème qui affirme que le problème SAT, c'est-à-dire le problème de satisfaisabilité d'une formule de la logique propositionnelle, est NP-complet. Il a...

turbo codes, l'approximation de l'énergie libre, et les modèles de satisfaisabilité. Cet algorithme fut proposé pour la première fois par Judea Pearl,...

fonction (un par quantification existentielle), tout en conservant la satisfaisabilité de la formule. La terminologie fait référence au logicien Thoralf Skolem...

logique Théorème de Löwenheim-Skolem Logique modale Théorie des modèles Satisfaisabilité Vérité Mates, Benson (1972), Elementary Logic, Second Edition, New...

dans des graphes aléatoires avec un degré donné,, des problèmes de satisfaisabilité aléatoire, de l'acyclic coloring, la décomposition arborescente, et...

Zypper. Elle repose sur un algorithme de résolution de dépendances par satisfaisabilité bien plus efficace, rapide et économe en mémoire que l'algorithme itératif...

transitions de phase pour les instances aléatoires du problème de satisfaisabilité. Il a prouvé un problème longtemps ouvert en informatique, la conjecture...

deux ou trois matroïdes, et dans 2-SAT et 3-SAT pour le problème de satisfaisabilité. Lenstra écrit que « Gene commenterait invariablement que c'est pour...

premier ordre[réf. nécessaire]. En 1999, W. Plandowski a démontré que la satisfaisabilité d'une équation de mots est dans PSPACE, alors que l'on ne connaissait...

En informatique théorique, le problème de satisfaisabilité d'un circuit (aussi connu sous le nom de CIRCUIT-SAT, CircuitSAT, CSAT[réf. nécessaire], etc...

logique d'origine. La complexité de calcul des tâches telles que la satisfaisabilité ou la vérification de modèle dans un fragment ne peut pas être plus...

et la planification Réécriture de termes et logique équationnelle Satisfaisabilité Sécurité Sémantique des langages de programmation Sujets émergents :...

Lemme local de Lovász (LLL), qui fournit des critères forts pour la satisfaisabilité des problèmes avec contraintes comme dans les formules de la logique...