PH (complexité)

En théorie de la complexité, PH est l'union des classes de complexité de la hiérarchie polynomiale :

{\mathsf {PH}}=\bigcup _{k\in \mathbb {N} }\Sigma _{k}^{\mathsf {P}}

PH a été introduite par Larry J. Stockmeyer en 1977^[1].

Propriétés[modifier | modifier le code]

PH est incluse dans PSPACE, la classe des problèmes de décision décidables en espace polynomial, mais la question de leur égalité, qui implique l'effondrement de la hiérarchie polynomiale, est un problème ouvert.

Si P=NP, alors P=PH et la hiérarchie polynomiale s'effondre au premier niveau.

Notes et références[modifier | modifier le code]

Références[modifier | modifier le code]

↑ (en) Larry J. Stockmeyer, « The polynomial-time hierarchy », Theoretical Computer Science, vol. 3, n^o 1,‎ 1^er octobre 1976, p. 1–22 (ISSN 0304-3975, DOI 10.1016/0304-3975(76)90061-X, lire en ligne, consulté le 15 mai 2021)

Bibliographie[modifier | modifier le code]

(en) Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 20 avril 2009, 579 p. (ISBN 978-0-521-42426-4, lire en ligne).
Sylvain Perifel, Complexité algorithmique, Éditions Ellipses, 22 avril 2014, 432 p. (ISBN 978-2-729-88692-9, lire en ligne).

Portail de l'informatique théorique

[1] (en) Larry J. Stockmeyer, « The polynomial-time hierarchy », Theoretical Computer Science, vol. 3, n^o 1,‎ 1^er octobre 1976, p. 1–22 (ISSN 0304-3975, DOI 10.1016/0304-3975(76)90061-X, lire en ligne, consulté le 15 mai 2021)

[1]