Class Description

coNP/poly: Complement of NP/poly

If NP is contained in coNP/poly then PH collapses to S2PNP [CCH+01].

NPNP^NP^(coNP/poly ∩ NP) = NPNP^NP [HNO+96]

Note: At the suggestion of Luis Antuñes, the above specimen of the Complexity Zoo has been locked in a cage.

Linked From

No class.