Metraipolis › archive › dc_c249593dbc3f
Hiérarchie booléenne — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Hi%C3%A9rarchie_bool%C3%A9enne
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-08T15:41:08.759Z
- SHA-256 of the archived text
0200d249ab921cc3ca61359e08bab3dc085cdad436c843a2b5068b613a9449a7- Stable URL of this page
https://metraipolis.com/documento/dc_c249593dbc3f
How to cite
Hiérarchie booléenne — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Hi%C3%A9rarchie_bool%C3%A9enne (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_c249593dbc3f (Metraipolis archive dc_c249593dbc3f, sha256 0200d249ab921cc3ca61359e08bab3dc085cdad436c843a2b5068b613a9449a7)
BibTeX
@misc{dcc249593dbc3f,
title = {Hiérarchie booléenne — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Hi%C3%A9rarchie_bool%C3%A9enne},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_c249593dbc3f; sha256 0200d249ab921cc3ca61359e08bab3dc085cdad436c843a2b5068b613a9449a7},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Hi%C3%A9rarchie_bool%C3%A9enne. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. 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 ( L 1 ∩ L 2 ) ∪ L 3 ¯ {\displaystyle {\overline {(L_{1}\cap L_{2})\cup L_{3}}}} appartient à la hiérarchie booléenne si L 1 {\displaystyle L_{1}} , L 2 {\displaystyle L_{2}} , L 3 {\displaystyle L_{3}} sont des langages de NP.
Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Hiérarchie booléenne» — https://fr.wikipedia.org/wiki/Hi%C3%A9rarchie_bool%C3%A9enne
Wikidata Q4943357: «hierarchy of complexity classes that can be constructed as boolean combinations of problems in the class NP» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q4943357
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Hi%C3%A9rarchie_bool%C3%A9enne?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 183945111, consultata il 2026-11-08T15:35:11.598Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 5eeae16d6f439f23da4fed343018d5e74ec4a769315d5edecd56751962d62653