Théorème de RiceEn informatique théorique, plus précisément en théorie de la calculabilité, le théorème de Rice énonce que toute propriété sémantique non triviale d'un programme est indécidable. Le théorème de Rice généralise l'indécidabilité du problème de l'arrêt. Le théorème est classique et fait l'objet d'exercices dans certains ouvrages de théorie de la calculabilité. Il a une certaine portée philosophique vis-à-vis de la calculabilité et est dû au logicien Henry Gordon Rice.
Quantum noiseQuantum noise is noise arising from the indeterminate state of matter in accordance with fundamental principles of quantum mechanics, specifically the uncertainty principle and via zero-point energy fluctuations. Quantum noise is due to the apparently discrete nature of the small quantum constituents such as electrons, as well as the discrete nature of quantum effects, such as photocurrents. Quantified noise is similar to classical noise theory and will not always return an asymmetric spectral density.
Exponential time hypothesisIn computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved in subexponential time, i.e., for all constant , where n is the number of variables in the formula. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement.
Fonction récursiveEn informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini. En fait, cela fait référence à deux concepts liés, mais distincts. En théorie de la calculabilité, la classe des fonctions récursives est une classe plus générale que celle des fonctions récursives primitives, mais plus restreinte que celle des fonctions semi-calculables (ou partielles récursives).
Randomized roundingWithin computer science and operations research, many combinatorial optimization problems are computationally intractable to solve exactly (to optimality). Many such problems do admit fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input. Randomized rounding is a widely used approach for designing and analyzing such approximation algorithms.
Registre quantiqueDans le domaine de l'informatique quantique, un registre quantique est un registre composé de plusieurs qubits , il est l'équivalent quantique d'un registre classique. Un registre quantique de taille est un système quantique comprenant qubits. Il peut être représenté sous la forme d'un espace de Hilbert, , dans lequel les données stockées sont sous la forme: Tout d'abord, il y a une différence conceptuelle entre le registre quantique et classique. Un registre classique de taille se compose d'un tableau de bascules.
Algorithme DPLLEn informatique, l'algorithme de Davis–Putnam–Logemann–Loveland (DPLL) est un algorithme de backtracking, complet, de résolution du problème SAT. Le problème SAT est un problème important à la fois d'un point de vue théorique, en particulier en théorie de la complexité où il est le premier problème prouvé NP-complet et pratique puisqu'il peut apparaître lors de la résolution de problèmes de planification classique, model checking, ou encore diagnostic et jusqu'au configurateur d'un PC ou de son système d'exploitation.
Sharp-P-complet#P-complet, prononcée "sharp P complet" ou "dièse P complet", est une classe de complexité en théorie de la complexité, un domaine de l'informatique théorique. Plus précisément, c'est l'ensemble des problèmes complets de la classe #P. Un problème X est dit #P-complet si et seulement s'il appartient à la classe #P, et si on peut réduire tout problème de #P à X par une réduction de comptage fonctionnant en temps polynomial.
Gap theoremSee also Gap theorem (disambiguation) for other gap theorems in mathematics. In computational complexity theory, the Gap Theorem, also known as the Borodin–Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable functions. It essentially states that there are arbitrarily large computable gaps in the hierarchy of complexity classes. For any computable function that represents an increase in computational resources, one can find a resource bound such that the set of functions computable within the expanded resource bound is the same as the set computable within the original bound.
Separable stateIn quantum mechanics, separable states are quantum states belonging to a composite space that can be factored into individual states belonging to separate subspaces. A state is said to be entangled if it is not separable. In general, determining if a state is separable is not straightforward and the problem is classed as NP-hard. Consider first composite states with two degrees of freedom, referred to as bipartite states. By a postulate of quantum mechanics these can be described as vectors in the tensor product space .
