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.
Oracle (machine de Turing)vignette|upright=2|Une machine de Turing avec oracle peut faire appel à une boîte noire (oracle). En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire. En particulier, l'oracle peut résoudre en temps constant un problème indécidable comme le problème de l'arrêt.
Résidu quadratiqueEn mathématiques, plus précisément en arithmétique modulaire, un entier naturel q est un résidu quadratique modulo n s'il possède une racine carrée en arithmétique modulaire de module n. Autrement dit, q est un résidu quadratique modulo n s'il existe un entier x tel que : Dans le cas contraire, on dit que q est un non-résidu quadratique modulo n Par exemple : modulo 4, les résidus quadratiques sont les entiers congrus à 2 ≡ 0 = 0 ou à (±1) = 1.
Crible quadratiqueL'algorithme du crible quadratique est un algorithme de factorisation fondé sur l'arithmétique modulaire. C'est en pratique le plus rapide après le crible général des corps de nombres, lequel est cependant bien plus compliqué, et n'est plus performant que pour factoriser un nombre entier d'au moins cent chiffres. Le crible quadratique est un algorithme de factorisation non spécialisé, c'est-à-dire que son temps d'exécution dépend uniquement de la taille de l'entier à factoriser, et non de propriétés particulières de celui-ci.
Fonction quadratiqueEn mathématiques, une fonction quadratique est une fonction de plusieurs variables polynomiale de degré 2. Cette notion généralise ainsi celle de fonction du second degré. Elle réalise aussi la partie régulière du développement de Taylor à l’ordre 2 pour une fonction de plusieurs variables. La matrice hessienne associée est la même en tout point, et ne dépend que de la forme quadratique constituée par les termes de degré 2. Elle permet aussi d’écrire le système d'équations linéaires qui détermine les points critiques de la fonction.
Entier quadratiqueEn mathématiques, un entier quadratique est un nombre complexe, racine d'un polynôme unitaire du second degré à coefficients entiers. La notion de nombre algébrique de degré inférieur ou égal à 2 est plus générale : elle correspond à un nombre complexe, racine d'un polynôme du second degré à coefficients seulement rationnels. Ces nombres particuliers disposent de propriétés algébriques.
Algorithme de ShorEn arithmétique modulaire et en informatique quantique, l’algorithme de Shor est un algorithme quantique conçu par Peter Shor en 1994, qui factorise un entier naturel N en temps O et en espace . Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implanté dans un calculateur quantique pratique. Un message chiffré avec RSA peut être déchiffré par factorisation de sa clé publique N, qui est le produit de deux nombres premiers.
Irrationnel quadratiqueUn irrationnel quadratique est un nombre irrationnel solution d'une équation quadratique à coefficients rationnels, autrement dit, un nombre réel algébrique de degré 2. Il engendre donc un corps quadratique réel Q(), où d est un entier positif sans facteur carré. Les irrationnels quadratiques sont caractérisés par la périodicité à partir d'un certain rang de leur développement en fraction continue (théorème de Lagrange). Les exemples les plus simples d'irrationnels quadratiques sont les racines carrées d'entiers naturels non carrés (le plus célèbre étant ).
Probabilité algorithmiqueEn théorie algorithmique de l'information, la probabilité algorithmique, aussi connue comme probabilité de Solomonoff, est une méthode permettant d’assigner une probabilité à une observation donnée. Il a été inventé par Ray Solomonoff dans les années 1960. Elle est utilisée dans la théorie de l'inférence inductive et dans l'analyse des algorithmes. En particulier, dans sa thèorie de l'induction, Solomonoff utilise une telle formulation pour exprimer la probabilité a priori dans la formule de Bayes.
Statistical randomnessA numeric sequence is said to be statistically random when it contains no recognizable patterns or regularities; sequences such as the results of an ideal dice roll or the digits of π exhibit statistical randomness. Statistical randomness does not necessarily imply "true" randomness, i.e., objective unpredictability. Pseudorandomness is sufficient for many uses, such as statistics, hence the name statistical randomness. Global randomness and local randomness are different.
DéterminismeLe déterminisme est une théorie philosophique selon laquelle chaque événement, en vertu du principe de causalité, est déterminé par les événements passés conformément aux lois de la nature. En physique, cette idée se traduit par la notion de système déterministe, c'est-à-dire un système soumis à une dynamique qui associe à chaque condition initiale un et un seul état final. On parle également de système déterministe en automatique pour désigner un système pour lequel les mêmes entrées produisent toujours exactement les mêmes sorties, par opposition à un système stochastique pour lequel les mêmes entrées peuvent produire différentes sorties.
Interprétations de la probabilitéLe mot probabilité a été utilisé dans une variété de domaines depuis qu'il a été appliqué à l'étude mathématique des jeux de hasard. Est-ce que la probabilité mesure la tendance réelle physique de quelque chose de se produire, ou est-ce qu'elle est une mesure du degré auquel on croit qu'elle se produira, ou faut-il compter sur ces deux éléments ? Pour répondre à ces questions, les mathématiciens interprètent les valeurs de probabilité de la théorie des probabilités.
