Problème NP-completEn théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l
AbonnementLe mot abonnement se réfère de manière générale à une souscription convenue entre un prestataire et un bénéficiaire pour un même service proposé en plusieurs fois ou sur une période donnée. Il peut renvoyer à plusieurs notions : Commande d'un lecteur à un éditeur de presse portant sur plusieurs parutions pour un titre donné ; Commande d'un spectateur à une entreprise de spectacles portant sur plusieurs représentations pour une saison donnée ; Commande d'un voyageur à une entreprise de transport portant sur l'acquisition d'un titre de transport valable pour une période donnée ou pour un nombre de courses définies.
NP (complexité)La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« en »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution.
Algorithme probabilisteEn algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].
Complet (complexité)En informatique théorique, et notamment en théorie de la complexité, un problème complet pour une classe de complexité est un problème de décision qui fait partie des problèmes les plus difficiles à résoudre de cette classe. En ce sens, il est un représentant de la classe. C'est une notion centrale en complexité. Elle permet notamment d'établir des inclusions entre les classes en ne considérant qu'un seul problème. Un problème p est dit difficile pour une classe C pour un certain type de réduction s'il existe une réduction de ce type, depuis n'importe quel problème de la classe vers p.
Logique de descriptionLes logiques de description aussi appelées logiques descriptives (LD) sont une famille de langages de représentation de connaissance qui peuvent être utilisés pour représenter la connaissance terminologique d'un domaine d'application d'une manière formelle et structurée. Le nom de logique de description se rapporte, d'une part à la description de concepts utilisée pour décrire un domaine et d'autre part à la sémantique basée sur la logique qui peut être donnée par une transcription en logique des prédicats du premier ordre.
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.
Hiérarchie polynomialeEn théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale. Il existe plusieurs définitions équivalentes des classes de la hiérarchie polynomiale. On peut définir la hiérarchie à l'aide des quantificateurs universel () et existentiel ().
Complexité en moyenne des algorithmesLa complexité en moyenne d'un algorithme est la quantité d'une ressource donnée, typiquement le temps, utilisée par l'algorithme lors de son exécution pour traiter une entrée tirée selon une distribution donnée. Il s'agit par conséquent d'une moyenne de la complexité, pondérée entre les différentes entrées possibles selon la distribution choisie. Le plus souvent, on ne précise pas la distribution et on utilise implicitement une distribution uniforme (i.e.
Théorie des graphesvignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.
