Problème P ≟ NPvignette|400px|Représentation visuelle des deux configurations possibles. Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable.
Formule booléenne quantifiéeEn théorie de la complexité, en informatique théorique, en logique mathématique, une formule booléenne quantifiée (ou formule QBF pour quantified binary formula en anglais) est une formule de la logique propositionnelle où les variables propositionnelles sont quantifiées. Par exemple, est une formule booléenne quantifiée et se lit « pour toute valeur booléenne x, il existe une valeur booléenne y et une valeur booléenne z telles que ((x ou z) et y) ».
Polynômethumb|Courbe représentative d'une fonction cubique. En mathématiques, un polynôme est une expression formée uniquement de produits et de sommes de constantes et d'indéterminées, habituellement notées X, Y, Z... Ces objets sont largement utilisés en pratique, ne serait-ce que parce qu'ils donnent localement une valeur approchée de toute fonction dérivable (voir l'article Développement limité) et permettent de représenter des formes lisses (voir l'article Courbe de Bézier, décrivant un cas particulier de fonction polynomiale).
Hardness of approximationIn computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. Hardness of approximation complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can be efficiently approximated. Typically such limits show a factor of approximation beyond which a problem becomes NP-hard, implying that finding a polynomial time approximation for the problem is impossible unless NP=P.
Problème SATvignette|Une instance du Sudoku peut être transformée en une formule de logique propositionnelle à satisfaire. Une assignation des variables propositionnelles donne une grille complétée. 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 propositionnelle, détermine s'il existe une assignation des variables propositionnelles qui rend la formule vraie. Ce problème est important en théorie de la complexité.
Méthode des tableauxvignette|200px|Représentation graphique d'un tableau propositionnel partiellement construit En théorie de la démonstration, les tableaux sémantiques sont une méthode de résolution du problème de la décision pour le calcul des propositions et les logiques apparentées, ainsi qu'une méthode de preuve pour la logique du premier ordre. La méthode des tableaux peut également déterminer la satisfiabilité des ensembles finis de formules de diverses logiques. C'est la méthode de preuve la plus populaire pour les logiques modales (Girle 2000).
SatisfaisabilitéEn logique mathématique, la satisfaisabilité ou satisfiabilité et la validité sont des concepts élémentaires de sémantique. Une formule est satisfaisable s'il est possible de trouver une interprétation (modèle), une façon d'interpréter tous les éléments constitutifs de la formule, qui rend la formule vraie. Une formule est universellement valide, ou en raccourci valide si, pour toutes les interprétations, la formule est vraie.
Polynôme formelEn algèbre, le terme de polynôme formel, ou simplement polynôme, est le nom générique donné aux éléments d'une structure construite à partir d'un ensemble de nombres. On considère un ensemble A de nombres, qui peut être celui des entiers ou des réels, et on lui adjoint un élément X, appelé indéterminée. La structure est constituée par les nombres, le polynôme X, les puissances de X multipliées par un nombre, aussi appelés monômes (de la forme aX), ainsi que les sommes de monômes. La structure est généralement notée A[X].
Règle de résolutionEn logique mathématique, la règle de résolution ou principe de résolution de Robinson est une règle d'inférence logique qui généralise le modus ponens. Cette règle est principalement utilisée dans les systèmes de preuve automatiques, elle est à la base du langage de programmation logique Prolog. La règle du modus ponens s'écrit et se lit : de p et de "p implique q", je déduis q. On peut réécrire l'implication "p implique q" comme "p est faux ou q est vraie". Ainsi, la règle du modus ponens s'écrit .
Démonstration constructiveUne première vision d'une démonstration constructive est celle d'une démonstration mathématique qui respecte les contraintes des mathématiques intuitionnistes, c'est-à-dire qui ne fait pas appel à l'infini, ni au principe du tiers exclu. Ainsi, démontrer l'impossibilité de l'inexistence d'un objet ne constitue pas une démonstration constructive de son existence : il faut pour cela en exhiber un et expliquer comment le construire. Si une démonstration est constructive, on doit pouvoir lui associer un algorithme.
