1
$\begingroup$

We know that $\mathsf{non-uniformAC^0\subsetneq PSPACE}$, $\mathsf{non-uniformACC^0\subsetneq NEXP}$. We know that $\mathsf{uniformACC^0=PH}$ is a possibility.

What are some of circuit separations that we know of?

What are some circuit separations that seem farthest apart but cannot be separated? By this question I mean that even though $\mathsf{uniformTC^0\subsetneq PH}$ is a possibility, an answer with $\mathsf{uniformACC^0\subsetneq PH}$ suffices since $\mathsf{uniformACC^0\subsetneq uniformTC^0}$ is hypothesized.

$\endgroup$
  • $\begingroup$ We know that $AC^0 \neq TC^0$. $\endgroup$ – Yuval Filmus Apr 29 '15 at 0:17
3
$\begingroup$

For all uniform classes $\operatorname{UF}$, for essentially any non-uniform class $\operatorname{NU}$, one will
have $\: \operatorname{NU} \not\subseteq \operatorname{UF} \:$, $\:$ since $\operatorname{NU}$ should be uncountable and $\operatorname{UF}$ is countable.
("Proof:" $\;\;\;$ By any reasonable definition of being uniform, for a language to be in $\operatorname{UF}$
there must be something in a particular at-most-countable set of things such that the
thing determines the language, so there are at most countably many languages in $\operatorname{UF}$.
On the other hand, for each subset $S$ of $\:\{\hspace{-0.03 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\hspace{-0.04 in}\}\:$,$\:$ the definition of $\operatorname{NU}$ should
mean that [the language consisting of exactly the strings whose length is in $S\hspace{.02 in}$] is in $\operatorname{NU}$.
In that case, since those languages are all different, $\operatorname{UF}$ will be uncountable.
"Therefore," one will have $\: \operatorname{NU} \not\subseteq \operatorname{UF} \;$.)

In particular, $\;\;\; \mathsf{non-uniformAC^0} \: \not\subseteq \: \operatorname{PSPACE} \;\;\;$ and
$\mathsf{non-uniformACC^0} \: \not\subseteq \: \operatorname{NEXP} \;\;\;$, $\;\;\;$ so both claims in your initial sentence are false.
It is far more interesting to ask which uniform classes
are subsets of which non-uniform classes.


$\operatorname{REG}$ $\: \not\subseteq \: \mathsf{non-uniformAC^0} \;\;\;$, $\;\;\;$ since $\;\;\;$ parity $\: \not\in \: \mathsf{non-uniformAC^0}$ $\:\:\:\:$.
$\operatorname{NEXP} \: \not\subseteq \: \mathsf{non-uniformACC^0} \;\;\;$; $\;\;\;$ which your question on cstheory was asking about.
$\operatorname{MA_{exp}}$ $\cap \hspace{.03 in}\operatorname{co-MA_{exp}}$ $\: \not\subseteq \:$ $\operatorname{P/poly}$ $\;\;\;$, $\;\;\;$ by page 16 of this paper.
$\operatorname{AM_{exp}}$ $\: \not\subseteq \:$ $\operatorname{(NP\cap coNP)/poly}$ $\;\;\;$, $\;\;\;$ by this paper. $\;\;\;\;\;$ (The right-hand-side of
the last non-containment is likely smaller than the class one would think it means.)
This paper shows that $\operatorname{MA_{exp}}$ can't be decided by circuits with "half-exponential" size.

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