Publication
Hardness Results for Consensus-Halving
Concepts associés (31)
NP-difficile
vignette|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.
Problème NP-complet
En 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
Problème du sac à dos
En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments décrits par leurs poids et valeurs.
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.
Problème P ≟ NP
vignette|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.
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.
Problème de décision
En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat.
E (nombre)
vignette|redresse|L’aire sous l’hyperbole est égale à 1 sur l’intervalle [1, e]. Le nombre e est la base des logarithmes naturels, c'est-à-dire le nombre défini par ln(e) = 1. Cette constante mathématique, également appelée nombre d'Euler ou constante de Néper en référence aux mathématiciens Leonhard Euler et John Napier, vaut environ 2,71828. Ce nombre est défini à la fin du , dans une correspondance entre Leibniz et Christian Huygens, comme étant la base du logarithme naturel.
Mathematical constant
A mathematical constant is a key number whose value is fixed by an unambiguous definition, often referred to by a special symbol (e.g., an alphabet letter), or by mathematicians' names to facilitate using it across multiple mathematical problems. Constants arise in many areas of mathematics, with constants such as e and pi occurring in such diverse contexts as geometry, number theory, statistics, and calculus. Some constants arise naturally by a fundamental principle or intrinsic property, such as the ratio between the circumference and diameter of a circle (pi).
Dureté (matériau)
La dureté d'un matériau est définie comme la résistance mécanique qu'un matériau oppose à la pénétration. Pour mesurer la dureté d'un matériau, un pénétrateur de faible déformabilité (cône ou sphère en diamant, carbure de tungstène lié au cobalt ou acier extra-dur) est enfoncé à la surface du matériau à tester avec une force connue pendant un temps donné. Plus l'empreinte laissée est petite, plus le matériau est dur. La dureté se mesure sur différentes échelles selon le type de matériau considéré.