The question concerns comparing the complexity classes ((X_{/F} \cap Y_{/F})) and ((X \cap Y)_{/F}), where (X) and (Y) are complexity classes and (F) is a set of advice functions (e.g., polynomial-length advice).

Definitions Clarified:

• (X_{/F}) (non-uniform (X) with (F)-advice): The class of languages decidable by a uniform machine (M) (from class (X)) using an (F...

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

Let us fix some notation that is standard in the advice-complexity literature.

• For a complexity class X and a set F of length functions,
X/F := { L ⊆ {0,1}* | ∃ f∈F , ∃ machine M∈X such that
∀x : M(x , f(|x|)) decides L }.

• We write X∩Y for the usual (uniform) intersection of classes.

The question is how the two constructions

  (i)  (X/F) ...

All the phenomena that lead to the confusion disappear once one writes the definitions carefully.
Fix two language classes X and Y and an “advice–length family’’ F (that is, a set of functions
f : N → N that we agree to regard as legal upper bounds on the length of the advice string).

Definitions
• X/F is the collection of languages L for which there exist

 – a length function f∈F,
 – an...

Excellent question. This is a classic and subtle point in complexity theory that touches upon the fundamental structure of complexity classes and the nature of advice.

Let's break down the issue, review the known results (which are mostly relativized), and discuss the current status.

Summary

The question of whether $(\mathsf{NP/poly} \cap \mathsf{coNP/poly}) = (\mathsf{NP} \cap \mathsf{coNP...

This is an interesting question about the relationship between intersection operations and advice in complexity theory. Let me provide a comprehensive answer.

The General Relationship

For complexity classes and with advice class , we always have:

This inclusion holds because if a language , then there exists an advice fun...

Below is a high–level summary of what is known (or not known) about the two ways of putting advice “inside” versus “outside” an intersection:

1. Definitions. Fix two (uniform) classes X,Y and a family of advice‐length bounds F (e.g. F={n^k: k∈ℕ}, so X/F = “X with polynomial advice”). We compare

   (i) X/F ∩ Y/F := {L: L∈X with some f∈F‐advice and L∈Y with (possibly a different) g∈F‐...

<think> We are given a question about the relationship between two types of intersections of complexity classes with advice. Specifically, the question references a statement by Abadi, Feigenbaum, and Kilian that it is not known whether NP/poly ∩ coNP/poly equals (NP ∩ coNP)/poly. The question asks for recent results comparing (X_{/F} ∩ Y_{/F}) and (X ∩ Y)_{/F} for complexity classes X and Y and a...

Intersecting Complexity Classes with Advice: Recent Results

The question concerns the relationship between and for complexity classes and with advice , specifically highlighting the case of versus .

Understanding the Containment

It's import...