Class Description

(NP ∩ coNP)/poly: Nonuniform NP ∩ coNP

Together with NP/poly ∩ coNP/poly, has the same relation to NP ∩ coNP as P/poly has to P. A language in (NP ∩ coNP)/poly is defined by a single language in NP ∩ coNP which is then modified by advice. A language in NP/poly ∩ coNP/poly comes from two possibly different languages in NP and coNP which become the same with good advice.

There is an oracle relative to which NP/poly ∩ coNP/poly, indeed NP/1 ∩ coNP/1, is not contained in (NP ∩ coNP)/poly [FFK+93]. Recently they improved this to NP/1 ∩ coNP [FF..].

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

Linked From

No class.