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
Graphe polyédriqueEn théorie des graphes, une branche des mathématiques, un graphe polyédrique est un graphe non orienté défini en termes géométriques : il représente les sommets et les arêtes d'un polyèdre convexe. On peut aussi définir un graphe polyédrique en termes purement issus de la théorie des graphes : c'est un graphe planaire 3 sommet-connexe. Le diagramme de Schlegel d'un polyèdre convexe représente ses sommets et ses arêtes par des points et des segments de droite dans le plan euclidien.
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.
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).
NP-difficilevignette|300px|Mise en évidence d'un problème NP-difficile si Problème P ≟ NP. Un problème NP-difficile est, en théorie de la complexité, un problème appartenant à la classe NP-difficile, ce qui revient à dire qu'il est au moins aussi difficile que les problèmes les plus difficiles de la classe NP. Ainsi, un problème H est NP-difficile, si tout problème L de la classe NP peut être réduit en temps polynomial à H. Si un problème NP-difficile est dans NP, alors c'est un problème NP-complet.
Peripheral cycleIn graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygons, because Tutte called cycles "polygons") were first studied by , and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.
Steinitz's theoremIn polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.
Équation polynomialeEn mathématiques, une équation polynomiale, ou équation algébrique, est une équation de la forme : où P est un polynôme. Voici un exemple d'équation simple avec une seule inconnue : Usuellement, le terme équation polynomiale désigne une équation avec une seule inconnue (notée ici x) : où l'entier naturel n et les , appelés coefficients de l’équation, sont connus. Les coefficients sont le plus souvent des nombres réels ou complexes, mais ils peuvent prendre leurs valeurs dans n’importe quel anneau.
Théorie de GaloisEn mathématiques et plus précisément en algèbre, la théorie de Galois est l'étude des extensions de corps commutatifs, par le biais d'une correspondance avec des groupes de transformations sur ces extensions, les groupes de Galois. Cette méthode féconde, qui constitue l'exemple historique, a essaimé dans bien d'autres branches des mathématiques, avec par exemple la théorie de Galois différentielle, ou la théorie de Galois des revêtements. Cette théorie est née de l'étude par Évariste Galois des équations algébriques.
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.
