# Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?

Let $$C$$ be an uniform complexity class for example $$NL$$ or $$NP$$. Is there distinction between $$(C/poly)\cap(coC/poly)$$ and $$(C\cap coC)/poly$$?

• What is $A/poly$ for an arbitrary complexity class? We usually define non uniform classes with respect to some underlying model, e.g. time/space bounded machines with advice. Jun 3, 2021 at 9:32
• @Ariel If $C$ is any class of languages, and $f\colon\mathbb N\to\mathbb N$, then $L\in C/f(n)$ iff there exists a language $L'\in C$ and a sequence of advice strings $\{a_n:n\in\mathbb N\}$ such that $|a_n|\le f(n)$ and $w\in L\iff(w,a_{|w|})\in L'$. Then $C/\mathrm{poly}=\bigcup_{c\in\mathbb N}C/n^c$. Jun 3, 2021 at 16:05

$$\def\co{\mathrm{co}}\def\poly{\mathrm{poly}}\def\N{\mathbb N}$$A language $$L$$ is in $$(C/\poly)\cap(\co C/\poly)$$ iff there are languages $$L_0\in C,\qquad L_1\in\co C,$$ and sequences of advice strings $$\{a_{0,n}:n\in\N\}$$, $$\{a_{1,n}:n\in\N\}$$ such that $$|a_{0,n}|,|a_{1,n}|=n^{O(1)},$$ and for any $$n\in\N$$ and $$w\in\{0,1\}^n$$, $$w\in L\iff(w,a_{0,n})\in L_0\iff(w,a_{1,n})\in L_1.$$ (I’m assuming the class $$C$$ is robust enough so that the exact representation of $$(w,a)$$ does not matter.)
In contrast, $$L$$ is in $$(C\cap\co C)/\poly$$ iff there exists a single language $$L'\in C\cap\co C$$ and a sequence of strings $$\{a'_n:n\in\N\}$$ such that $$|a'_n|=n^{O(1)},$$ and for any $$w\in\{0,1\}^n$$, $$w\in L\iff(w,a_n)\in L'.$$
Thus, we trivially have the inclusion $$(C\cap\co C)/\poly\subseteq(C/\poly)\cap(\co C/\poly)$$ as we can just put $$L_0=L_1:=L'$$, $$a_{0,n}=a_{1,n}:=a'_n$$. However, there is no a priori reason for the reverse inclusion to hold: while we can easily combine $$a_{0,n}$$ and $$a_{1,n}$$ to a single advice $$a'_n=(a_{0,n},a_{1,n})$$, there is in general no way how to unify $$L_0\in C$$ and $$L_1\in\co C$$ to a single language $$L'\in C\cap\co C$$.
For the specific examples, it seems reasonable to conjecture that $$\def\np{\mathrm{NP}}(\np\cap\co\np)/\poly\subsetneq(\np/\poly)\cap(\co\np/\poly),$$ but since this implies various hard separations (in particular, $$\np\ne\co\np$$ and $$\np\nsubseteq\mathrm P/\poly$$), we don’t know how to prove that.
On the other hand, the Immerman–Szelepcsényi theorem ensures that $$\def\nl{\mathrm{NL}}\nl=\co\nl$$, hence $$\nl/\poly=\co\nl/\poly=(\nl/\poly)\cap(\co\nl/\poly)=(\nl\cap\co\nl)/\poly.$$
For an example (even if a bit contrived) with an unconditional separation, let $$\def\nul{\mathrm{NULL}}\nul$$ denote the class of languages of asymptotic density $$0$$: i.e., if $$L\subseteq\{0,1\}^*$$, then $$L\in\nul\iff\lim_{n\to\infty}\frac{|L\cap\{0,1\}^n|}{2^n}=0.$$ Then $$\nul\cap\co\nul=\varnothing$$, hence also $$(\nul\cap\co\nul)/\poly=\varnothing.$$ On the other hand, $$(\nul/\poly)\cap(\co\nul/\poly)$$ is the class of all languages: for any language $$L$$, define $$L_0=\{(w,0^n):w\in L,n=|w|\}\in\nul$$ and $$L_1=\overline{\{(w,0^n):w\in\overline L,n=|w|\}}\in\co\nul.$$ Then we have $$w\in L\iff(w,0^n)\in L_0\iff(w,0^n)\in L_1$$ for any $$w\in\{0,1\}^n$$.