Class Description

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.

Linked From

ELkP: Extended Low Hierarchy

An extension of LkP.

The class of problems A such that ΣkPA is contained in Σk-1PA,NP.

Defined in [BBS86].

More about...


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.

More about...