Short answer
- In general, (X ∩ Y)/F ⊆ X/F ∩ Y/F always holds, but the reverse inclusion need not hold.
- For most interesting pairs of classes (in particular X = NP and Y = coNP with F = poly), it is still open whether equality holds. In particular, it remains open whether
NP/poly ∩ coNP/poly = (NP ∩ coNP)/poly.
- There are no known unconditional separations for natural classes like NP and coNP; on the other hand, relativized separations are known (i.e., there are oracles relative to which the two sides differ).
- If X = Y (or one contains the other) and is closed under intersection, then equality holds trivially: (X ∩ X)/F = X/F = X/F ∩ X/F.
- If one works with promise classes (rather than language classes), the two notions coincide; this is one reason advice is often most naturally treated in the promise setting.
Why the inclusion can be strict
The subtle point (and the source of the confusion in the AFK conference version) is the following. If L ∈ X/F ∩ Y/F, then there exist:
- A language A ∈ X and an advice function a(·) such that x ∈ L iff ⟨x, a(|x|)⟩ ∈ A, and
- A language B ∈ Y and an advice function b(·) such that x ∈ L iff ⟨x, b(|x|)⟩ ∈ B.
Even if you concatenate the advices to form a single advice string c(n) = ⟨a(n), b(n)⟩, this only shows that there are two (possibly different) pair-languages A′ ∈ X and B′ ∈ Y that both decide L using the same advice c. To conclude L ∈ (X ∩ Y)/F, you would need a single pair-language C that lies in X ∩ Y (i.e., C ∈ X and C ∈ Y simultaneously) and works with the single advice c. In general, there is no reason A′ = B′ or that either A′ or B′ lies in both X and Y. Thus the concatenation trick does not give the desired equality.
What is known
- For NP vs. coNP with polynomial advice, the question remains open: it is still not known whether NP/poly ∩ coNP/poly equals (NP ∩ coNP)/poly. This is the exact issue highlighted by Abadi, Feigenbaum, and Kilian (AFK).
- The operators “intersection” and “advice” do not commute in general; there are relativized worlds where they differ. In particular, one can construct oracles O such that
(NP^O ∩ coNP^O)/poly ⊊ NP^O/poly ∩ coNP^O/poly.
(This kind of separation is obtained by standard oracle-diagonalization/hiding-information techniques; see discussions in texts and surveys on advice and relativization.)
- For classes closed under intersection and complement (e.g., P, BPP, PSPACE), the issue is trivial: since X = coX and X is closed under ∩, we have X/poly ∩ X/poly = X/poly = (X ∩ X)/poly.
- For promise versions of these classes (e.g., promise-NP, promise-coNP), the two constructions are equivalent, because the “pair-language” only needs to be correct on the promise (the specific advice strings), so one can freely modify behavior off the promise to make the two verifiers coincide. This is why in many works advice is treated via promise classes to avoid exactly this pitfall.
References and pointers
- Abadi, Feigenbaum, and Kilian, On hiding information from an oracle, JCSS 1989. They explicitly note the (then) mistaken identification and correct it; the equality remains open.
- For background on advice classes and these closure subtleties (including relativized separations and the role of promise problems), see standard references/surveys such as:
- Hemaspaandra and Ogihara, The Complexity Theory Companion (sections on nonuniformity/advice and relativization).
- Lecture notes and surveys on nonuniform complexity/advice (e.g., by Allender, Fortnow, or Goldreich) discussing promise vs. language formulations and closure properties.
To summarize: beyond the trivial cases (X = Y or containment), there is no general unconditional theorem equating X/F ∩ Y/F with (X ∩ Y)/F, and the NP vs. coNP case with polynomial advice is still open. In promise settings the two coincide, and there are relativized separations showing that, as language classes, the two operators need not commute.