Skip to main content
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Source Link

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

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.

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.

Source Link
user12859
user12859

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.