# P/Poly vs Uniform Complexity Classes

It is not known whether NEXP is contained in P/poly. Indeed proving that NEXP is not in P/poly would have some applications in derandomization.

1. What is the smallest uniform class C for which one can prove that C is not contained in P/poly?

2. Would showing that co-NEXP is not contained in P/poly have some other complexity theoretic consequences as in the case NEXP vs P/poly?

Note: I'm aware that $SP_2$ is known not to be contained in $Size[n^k]$ for each fixed constant $k$ (This was also shown for MA with 1 bit of advice). But in this question I'm not interested in results for fixed $k$. I'm really interested in classes which are different from P/Poly, even if these classes are very large.

• You are essentially asking for a problem with superpolynomial size lower bounds for general circuits. Commented Jun 19, 2016 at 22:39
• $\mathsf{MA}_\mathrm{exp}$ is known to not be in $\mathsf{P/poly}$. See the Wikipedia article for a short proof. Commented Jun 19, 2016 at 22:46
• P/poly is closed under complement, so it contains NEXP if and only if it contains coNEXP. Commented Jun 20, 2016 at 8:11
• Emil, Robin and Andrew, thanks for your answers. I think my question can be considered to be answered now. Would somebody write it in an answer so that I can accept it? Commented Jun 20, 2016 at 15:35
• I believe that $MA_{exp}$ is the smallest uniform class with known superpolynomial lower bounds (people.cs.uchicago.edu/~fortnow/papers/nonrel.pdf), and that $O^P_2$ is the smallest one with arbitrary polynomial lower bounds (citeseerx.ist.psu.edu/viewdoc/…). Commented Jun 21, 2016 at 18:33

$$\let\mr\mathrm$$There are several results in the literature stating that a certain class $$C$$ satisfies $$C\nsubseteq\mr{SIZE}(n^k)$$ for any $$k$$, and usually it is straightforward to pad them to show that any barely superpolynomially expanded version of $$C$$ is not in $$\mr{P/poly}$$.

Let me say that $$f\colon\mathbb N\to\mathbb N$$ is a superpolynomial bound if it is time-constructible and $$f(n)=n^{\omega(1)}$$. For example, $$n^{\log\log\log\log n}$$ is a superpolynomial bound. In fact, an instructive exercise shows that if $$g(n)$$ is any unbounded monotone computable function, there is a superpolynomial bound $$f$$ such that $$f(n)\le n^{g(n)}$$.

First, direct diagonalization shows that $$\Sigma_4^P\nsubseteq\mr{SIZE}(n^k)$$ for any $$k$$. The same argument gives:

• If $$f$$ is any superpolynomial bound, then $$\Sigma_4\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$$.

Proof sketch: For any $$n$$, let $$C_n$$ be the lexicographically first circuit of size $$2f(n)$$ that computes a Boolean function in $$n$$ variables not computable by a circuit of size $$. Then, the language $$L$$ defined by $$x\in L\iff C_{|x|}(x)=1$$ works.

A well-known improvement states that $$S_2\mr P\nsubseteq\mr{SIZE}(n^k)$$ for any $$k$$. Likewise,

• If $$f$$ is any superpolynomial bound, then $$S_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$$.

Proof sketch: If not, then in particular $$\mr{NP}\subseteq S_2\mr P\subseteq\mr{P/poly}$$, hence $$\mr{PH}=S_2\mr P$$. By a padding argument, $$\Sigma_4\text-\mr{TIME}(f(n))\subseteq S_2\text-\mr{TIME}(f(n))\subseteq\mr{P/poly}$$, quod non.

Oblivious classes do even better. Taking into account the objection raised by Apoorva Bhagwat, let $$\mr{NLin=NTIME}(n)$$. Then $$\mr{NLin}\cup O_2\mr P\nsubseteq\mr{SIZE}(n^k)$$ for any $$k$$, and the same argument yields:

• If $$f$$ is any superpolynomial bound, then $$\mr{NLin}\cup O_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$$.

Proof sketch: If $$\mr{NLin\subseteq P/poly}$$, then by padding, $$\mr{NP\subseteq P/poly}$$, which implies $$\mr{PH}=O_2\mr P$$. Then we proceed as before.

In fact, we do have $$O_2\mr P\nsubseteq\mr{SIZE}(n^k)$$ for all $$k$$ due to a recent result of Li, who proved that there is a single-valued $$\mr{FS_2P}$$ algorithm solving the range-avoidance problem (aka dWPHP or sWPHP, as it is known in bounded arithmetic literature). Given an input $$w\in\{0,1\}^n$$, we can apply the range-avoidance algorithm to the function that takes a circuit $$\{0,1\}^{(k+1)\log n}\to\{0,1\}$$ of size $$n^k$$, and outputs its truth table; this gives us a Boolean function $$h\colon\{0,1\}^{(k+1)\log n}\to\{0,1\}$$ that requires circuit size $$n^k$$, and we apply it to the first $$(k+1)\log n$$ bits of $$w$$. This yields an $$S_2\mr P$$ language, which is oblivious (i.e., $$O_2\mr P$$) because we only use $$n$$ (rather than $$w$$) to find $$h$$.

(Note, by the way, that $$O_2\mr P\subseteq\mr{P/poly}$$.)

Now, pretty much the same argument applied to functions $$\{0,1\}^{\log f(n)}\to\{0,1\}$$ shows:

• If $$f$$ is any superpolynomial bound, then $$O_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$$.

These arguments are spelled out in Gajulapalli, Li & Volkovich.

There are also results involving MA. The often mentioned result that $$\mr{MA\text-EXP\nsubseteq P/poly}$$ is an overkill. Santhanam proved $$\mr{promise\text-MA\cap promise\text-coMA\nsubseteq SIZE}(n^k)$$ for any $$k$$, and a similar argument gives:

• If $$f$$ is any superpolynomial bound, then $$\mr{promise\text-MA\text-TIME}(f(n))\cap\mr{promise\text-coMA\text-TIME}(f(n))\nsubseteq\mr{P/poly}.$$

Proof sketch: By Santhanam’s Lemma 11 (which is a sharpened version of the standard fact that $$\mr{PSPACE=IP}$$ with a PSPACE prover), there is a PSPACE-complete language $$L$$ and a randomized poly-time oracle TM $$M$$ such that on input $$x$$, $$M$$ only asks oracle queries of length $$|x|$$; if $$x\in L$$, then $$M^L(x)$$ accepts with probability $$1$$; and if $$x\notin L$$, then for any oracle $$A$$, $$M^A(x)$$ accepts with probability $$\le1/2$$.

For a suitable monotone polynomial $$p$$, let $$A=(A_{\mr{YES}},A_{\mr{NO}})$$ be the promise problem defined by \begin{align} (x,s)\in A_{\mr{YES}}&\iff\exists\text{circuit }C\,\bigl(p(|C|+|x|)\le f(|s|)\land\Pr[M^C(x)\text{ accepts}]=1\bigr),\\ (x,s)\in A_{\rlap{\mr{NO}}\phantom{YES}}&\iff\forall\text{circuit }C\,\bigl(p(|C|+|x|)\le f(|s|)\to\Pr[M^C(x)\text{ accepts}]\le1/2\bigr). \end{align} Let $$h(x)$$ be a polynomial reduction of $$L$$ to its complement, and let $$B=(B_{\mr{YES}},B_{\mr{NO}})$$ be the promise problem \begin{align} (x,s)\in B_{\mr{YES}}&\iff(x,s)\in A_{\mr{YES}}\land(h(x),s)\in A_{\mr{NO}},\\ (x,s)\in B_{\rlap{\mr{NO}}\phantom{YES}}&\iff(x,s)\in A_{\mr{NO}}\land(h(x),s)\in A_{\mr{YES}}. \end{align} If $$p(n)$$ is chosen suitably large, $$B\in\mr{promise\text-MA\text-TIME}(f(n))\cap\mr{promise\text-coMA\text-TIME}(f(n)).$$ So, let us assume for contradiction that $$B$$ has polynomial-size circuits, say, $$B\in\mr{SIZE}(n^k)$$. Let $$s(n)$$ denote the size of the smallest circuit computing $$L$$ on inputs of length $$n$$, and put $$t(n)=f^{-1}(p(s(n)))$$; more precisely, $$t(n)=\min\{m:p(s(n))\le f(m)\}.$$ Then $$x\mapsto(x,1^{t(n)})$$ is a reduction of $$L$$ to $$B$$, thus $$L\in\mr{SIZE}(t(n)^k)$$, which means $$s(n)\le t(n)^k.$$ But since $$f$$ is superpolynomial, we have $$t(n)=s(n)^{o(1)}$$. This gives a contradiction for $$n$$ sufficiently large.

If we prefer a result with a non-promise version of MA, Miltersen, Vinodchandran, and Watanabe proved $$\mr{MA\text-TIME}(f(n))\cap\mr{coMA\text-TIME}(f(n))\nsubseteq\mr{P/poly}$$ for a half-exponential function $$f$$. We can improve it in two ways: first, it holds for $$\tfrac1k$$-exponential bounds for any constant $$k$$, and second, it holds for oblivious classes. Here, a $$\tfrac1k$$-exponential function is, roughly speaking, a function $$f$$ such that $$\underbrace{f\circ\dots\circ f}_k=\exp$$. See the Miltersen–Vinodchandran–Watanabe paper and references therein for the precise definition; it involves a well-behaved family of well-behaved functions $$e_\alpha(x)$$, $$\alpha\in\mathbb R_+$$, such that $$e_0(x)=x$$, $$e_1(x)=e^x-1$$, and $$e_{\alpha+\beta}=e_\alpha\circ e_\beta$$. Also, if $$f(n)\le e_\alpha(\mr{poly}(n))$$ and $$g(n)\le e_\beta(\mr{poly}(n))$$, then $$f(g(n))\le e_{\alpha+\beta}(\mr{poly}(n))$$. Then we have:

• $$\mr{OMA\text-TIME}(e_\alpha)\cap\mr{coOMA\text-TIME}(e_\alpha)\nsubseteq\mr{P/poly}$$ for any $$\alpha>0$$.

Proof sketch: Assume otherwise. Fix an integer $$k$$ such that $$1/k<\alpha$$. Let me abbreviate $$\mr{OcOMT}(f)=\mr{OMA\text-TIME}(\mr{poly}(f(\mr{poly}(n)))\cap\mr{coOMA\text-TIME}(\mr{poly}(f(\mr{poly}(n))).$$ By padding, we have $$\tag{1}\mr{OcOMT}(e_{\beta+1/k})\subseteq\mr{SIZE}(e_\beta(\mr{poly}(n)))$$ for any $$\beta\ge0$$. Moreover, using e.g. Santhanam’s Lemma 11 above, we have the implication $$\tag{2}\mr{PSPACE\subseteq SIZE}(e_\beta(\mr{poly}(n)))\implies\mr{PSPACE\subseteq OcOMT}(e_\beta).$$ Since trivially $$\mr{PSPACE\subseteq OcOMT}(e_1)$$, a repeated application of (1) and (2) shows $$\mr{PSPACE\subseteq SIZE}(e_{(k-1)/k}(\mr{poly}(n)))$$, $$\mr{PSPACE\subseteq OcOMT}(e_{(k-1)/k})$$, $$\mr{PSPACE\subseteq SIZE}(e_{(k-2)/k}(\mr{poly}(n)))$$, $$\mr{PSPACE\subseteq OcOMT}(e_{(k-2)/k})$$, and so on. After $$k$$ steps, we reach $$\mr{PSPACE\subseteq P/poly}\qquad\text{and}\qquad\mr{PSPACE=OMA\cap coOMA}.$$ Using padding once more, we get $$\mr{DSPACE}(e_{1/k})\subseteq\mr{OcOMT}(e_{1/k})\subseteq\mr{P/poly},$$ which contradicts the results above, as $$e_{1/k}$$ is a superpolynomial bound.

Since nobody posted an answer, I will answer the question myself with the comments posted in the original question. Thanks to Robin Kothari, Emil Jerabek, Andrew Morgan and Alex Golovnev.

$MA_{exp}$ seems to be the smallest uniform class with known superpolynomial lower bounds.

$O_2^P$ seems to be the smallest known class not having circuits of size $n^k$ for each fixed $k$.

By diagonalization, it follows that for any super-polynomial (and space-constructible) function $s$, $DSPACE[s(n)]$ doesn't have polynomial-size circuits. $PSPACE$ versus $P/poly$ is still open.

$P/poly$ is closed under complement, so it contains $NEXP$ if and only if it contains $coNEXP$.

Please correct me if I'm wrong, but as far as I can tell, we actually don't know a fixed-polynomial size lower bound for $O_2^P$. This is because the usual Karp-Lipton argument doesn't go through for $O_2^P$, since we don't know whether $\textsf{NP}\subseteq O_2^P$ (in fact, this is equivalent to asking whether $\textsf{NP}\subseteq \textsf{P/poly}$). However, we do know that $\textsf{NP}^{O_2^P}$ isn't contained in $\textsf{SIZE}(n^k)$ for any $k$, as shown by Chakaravarthy and Roy.

• Six years later, it turns out $O^P_2$ does actually contain languages requiring size-$n^k$ circuits for any constant $k$. This follows from recent results of Li (eccc.weizmann.ac.il/report/2023/156). Commented May 3 at 11:34