1
$\begingroup$

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$?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ariel
    Jun 3, 2021 at 9:32
  • $\begingroup$ @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$. $\endgroup$ Jun 3, 2021 at 16:05

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.