Loading AI tools
hiérarchie de classes de complexité obtenues comme combinaisons booléennes de problèmes de décision de NP De Wikipédia, l'encyclopédie libre
En informatique théorique, plus précisément en théorie de la complexité, la hiérarchie booléenne (notée BH pour Boolean hierarchy en anglais) est une hiérarchie de classes de complexité obtenues comme combinaisons booléennes (intersections, unions, et passage au complémentaire) de problèmes de décision de NP[1]. Plus précisément, un langage/problème de décision dans la hiérarchie booléenne s'écrit comme une « formule booléenne » où les « variables » sont des langages de NP, par exemple appartient à la hiérarchie booléenne si , , sont des langages de NP.
On définit BHi par récurrence sur i :
BH est l'union des BHi.
BH2 est noté DP (Difference Polynomial Time)[2].
Si la hiérarchie booléenne s'effondre, alors la hiérarchie polynomiale s'effondre à Σ3P[3],[4]. Elle est incluse dans Δ2P.
Le problème MAX-CLIQUE, étant donné un graphe non orienté G et un entier k, savoir si une clique maximale de G est de taille k, est DP-complet[2].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.