PH (complexité)

Dans la théorie de complexité informatique , le pH de la classe de complexité de est l'union de toutes les classes de complexité dans la hiérarchie polynôme :

$\ mbox {pH} = \ bigcup_ {k \ dans \} de mathbb {N} \ Delta_k \ mbox {P}$

Le pH a été défini la première fois par le Larry Stockmeyer . Il est contenu dans le P^PP (la classe des problèmes qui sont que l'on peut décider par une machine polynôme de Turing de de temps avec l'accès à un oracle du pp ), le P^#P (par le théorème de Toda de ), et également dans le PSPACE .

Le pH a une caractérisation logique simple : c'est l'ensemble de langues exprimables par la logique de second ordre .

Le pH contient presque toutes les classes bien connues de complexité à l'intérieur du PSPACE ; en particulier, il contient le P , le NP , et le Co-NP . Il contient même les classes probabilistes telles que le BPP et le RP .

P = NP si et seulement si P = pH . Ceci peut simplifier une preuve potentielle de &ne du P ; NP , puisqu'il est seulement nécessaire de séparer le P du plus général pH de classe.

Random links: