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.
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.