L (complexité)En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée. Pour être plus précis, l'exigence sur l'espace de taille logarithmique se réfère à l'espace supplémentaire utilisable. Elle est aussi parfois notée LOGSPACE.
Diagramme de décision binaireEn informatique, un graphe de décision binaire ou diagramme de décision binaire (ou BDD pour Binary Decision Diagram en anglais) est une structure de données utilisée pour représenter des fonctions booléennes, ou des questionnaires binaires. On utilise les BDD pour représenter des ensembles ou des relations de manière compacte / compressée. Les diagrammes de décision binaires sont utilisés par les programmes de conception assistée par ordinateur (CAO / CAD) pour générer des circuits (synthèse logique), et dans la vérification formelle.
Hypothèse calculatoireEn cryptographie, une hypothèse de difficulté calculatoire est une hypothèse qui sert à évaluer et à démontrer la robustesse des primitives cryptographiques. Dans certains cas, la sécurité est dite inconditionnelle si elle ne repose sur aucune hypothèse de difficulté calculatoire ; un exemple courant est la technique dite du masque jetable, où le masque est aussi grand que le message. Cependant, il est souvent impossible d'atteindre une forme de sécurité aussi forte ; dans de tels cas, les cryptographes doivent s'en remettre à une forme de sécurité dite « calculatoire ».
Programmation par contraintesLa programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement. En programmation par contraintes, on sépare la partie modélisation à l'aide de problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem), de la partie résolution dont la particularité réside dans l'utilisation active des contraintes du problème pour réduire la taille de l'espace des solutions à parcourir (on parle de propagation de contraintes).
Synthèse de programmesEn informatique, la synthèse de programmes consiste à construire automatiquement un programme à partir d'une spécification. La spécification est décrite dans un langage logique, par exemple en logique temporelle linéaire. La synthèse de programmes s'appuie sur des techniques de vérification formelle de programmes. Le problème de synthèse de programmes remonte aux travaux d'Alonzo Church. Manna et Waldinger ont proposé une méthode déductive pour synthétiser un programme à partir d'une spécification en logique du premier ordre.
Forme normale disjonctiveEn logique booléenne ou en calcul des propositions, une forme normale disjonctive ou FND (en anglais, disjunctive normal form ou DNF) est une normalisation d'une expression logique qui est une disjonction de clauses conjonctives. Elle est utilisée dans la démonstration automatique de théorèmes. Une expression logique est en FND si et seulement si elle est une disjonction d'une ou plusieurs conjonctions d'un ou plusieurs littéraux. Tout comme dans une forme normale conjonctive (FNC), les seuls opérateurs dans une FND sont le et logique, le ou logique et la négation.
P/polyEn informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales. Cette classe a été introduite par Karp et Lipton en 1980. Cette classe est importante, car comme P est incluse dans P/poly, si on démontre que NP ⊈ P/poly, alors on résout le problème ouvert P est différent de NP. Il y a deux définitions équivalentes, la première donnée avec le modèle de calcul des circuits booléens, l'autre avec des machines de Turing.
NP-intermédiaireEn théorie de la complexité, un problème NP-intermédiaire est un problème dans NP, qui n'est ni NP-complet et ni dans P. La classe des problèmes NP-intermédiaires se note NPI. Richard Emil Ladner a démontré en 1975, que sous l'hypothèse que P ≠ NP, NPI est non vide, c'est le théorème de Ladner. Pour prouver ce théorème, Ladner a construit un problème artificiel sans application pratique. On ne sait pas si des problèmes naturels dans NPI existent, mais il existe un grand nombre de problèmes dont on ne sait pas dans quelle classe ils se trouvent.
Problème 2-SATEn informatique théorique, le problème 2-SAT est un problème de décision. C'est une restriction du problème SAT qui peut être résolu en temps polynomial, alors que le problème général est NP complet. Le problème 2-SAT consiste à décider si une formule booléenne en forme normale conjonctive, dont toutes les clauses sont de taille 2, est satisfaisable. De telles formules sont appelées 2-CNF ou formules de Krom. On considère des formules en forme normale conjonctive, c'est-à-dire que ce sont des ET de OU de littéraux (un littéral est une variable ou la négation d'une variable).
Horn-satisfiabilitéUne formule de Horn est une conjonction de clauses contenant chacune au plus un littéral positif, c'est-à-dire une conjonction de clauses de Horn. Puisque le problème SAT est NP-complet, donc vérifiable en temps polynomial et plus difficile que tout problème dans NP, il est naturel de rechercher des problèmes 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 difficile que tout problème dans P.
