PH (complexité)

classe de complexité algorithmique

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

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

PropriétésModifier

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érencesModifier

RéférencesModifier

  1. (en) Larry J. Stockmeyer, « The polynomial-time hierarchy », Theoretical Computer Science, vol. 3, no 1,‎ , p. 1–22 (ISSN 0304-3975, DOI 10.1016/0304-3975(76)90061-X, lire en ligne, consulté le )

BibliographieModifier