Class Description

HkP: High Hierarchy In NP

The class of problems A in NP such that ΣkPA = Σk+1P; that is, adding A as an oracle increases the power of the kth level of the polynomial hierarchy by a maximum amount.

For all k, Hk is contained in Hk+1.

H0 consists exactly of the problems complete for NP under Cook reductions.

H1 consists exactly of the problems complete for NP under strong non-deterministic Turing reductions [Sch83].

Defined in [Sch83].

See also LkP.

Linked From

LkP: Low Hierarchy In NP

The class of problems A such that ΣkPA = ΣkP; that is, adding A as an oracle does not increase the power of the kth level of the polynomial hierarchy.

L1P = NP ∩ coNP.

For all k, Lk is contained in Lk+1 and in NP.

Defined in [Sch83].

See also HkP.

More about...