En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3.
La classe BPP est l'ensemble des problèmes, ou de façon équivalente des langages, pour lesquels il existe une machine de Turing probabiliste en temps polynomial qui satisfait les conditions d'acceptation suivantes :
Si le mot n'est pas dans le langage, la machine le rejette avec une probabilité supérieure à 2/3.
Si le mot est dans le langage, la machine l'accepte avec une probabilité supérieure à 2/3.
Autrement dit la machine se trompe avec une probabilité inférieure à 1/3.
On définit la classe BPP comme l'ensemble des langages tels qu'il existe un polynôme et un langage vérifiants que pour tout mot :
On peut utiliser une machine probabiliste pour faire un calcul déterministe, et donc P BPP. L'autre inclusion est une question ouverte. En terme plus généraux, la question est de savoir si l'aléatoire est utile pour accélérer le calcul ou non. Il y a eu à ce sujet un changement d'avis de la part de la communauté de la complexité : jusqu'aux années 80, la plupart des chercheurs pensaient que BPP était différente de P, puis divers résultats ont bousculé cette croyance. Aujourd'hui une égalité est souvent envisagée.
thumb|Inclusions de classes de complexité probabilistes.
BPP contient aussi les classes probabilistes dont les conditions d'acceptation sont plus fortes ZPP, RP et co-RP.
Avec les notations de la hiérarchie polynomiale, on a d'après le théorème de Sipser–Gács–Lautemann.
Dans le monde des classes de circuits booléens, le théorème d'Adleman donne BPP P/poly .
La variante quantique de BPP est BQP.
On peut avoir des machines plus efficaces si nécessaire, autrement dit on peut remplacer 2/3 par et 1/3 par (pour tout petit), en ne changeant pas la classe. Ce renforcement peut être effectué en lançant plusieurs fois la machine de façon indépendante et en faisant un vote.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Probabilistic proof systems (eg PCPs and IPs) have had a tremendous impact on theoretical computer science, as well as on real-world secure systems. They underlie delegation of computation protocols a
After introducing the foundations of classical and quantum information theory, and quantum measurement, the course will address the theory and practice of digital quantum computing, covering fundament
The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC
En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
L'informatique quantique est le sous-domaine de l'informatique qui traite des calculateurs quantiques et des associés. La notion s'oppose à celle d'informatique dite « classique » n'utilisant que des phénomènes de physique classique, notamment de l'électricité (exemple du transistor) ou de mécanique classique (exemple historique de la machine analytique). En effet, l'informatique quantique utilise également des phénomènes de la mécanique quantique, à savoir l'intrication quantique et la superposition.
En 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].
Explore la propagation des croyances sur les arbres, discutant des marges des cavités, des algorithmes de transmission de messages et du calcul de l'entropie libre.
Couvre la méthode Quadratic Sieve pour la factorisation entière, soulignant l'importance de choisir les bons paramètres pour la factorisation efficace.
Succinct non-interactive arguments of knowledge (SNARKs) are cryptographic proofs with strong efficiency properties. Applications of SNARKs often involve proving computations that include the SNARK verifier, a technique called recursive composition. Unfort ...
We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-d Sherali-Adams refutation of an unsatisfiable CNF formula C if and only if there is an ε > 0 and a degree-d conical junta J such that viol_C(x) - ε = J, where ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022
Objective. Accurate decoding of individual finger movements is crucial for advanced prosthetic control. In this work, we introduce the use of Riemannian-space features and temporal dynamics of electrocorticography (ECoG) signal combined with modern machine ...