<p>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. </p>

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

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

<p>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>

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

CC BY-SA 3.0
2016-07-20T13:34:37.337Z
2016-07-20T13:34:37.337Z
Springberg
<p><span class="math-container">$\let\mr\mathrm$</span>There are several results in the literature stating that a certain class <span class="math-container">$C$</span> satisfies <span class="math-container">$C\nsubseteq\mr{SIZE}(n^k)$</span> for any <span class="math-container">$k$</span>, and usually it is straightforward to pad them to show that any barely superpolynomially expanded version of <span class="math-container">$C$</span> is not in <span class="math-container">$\mr{P/poly}$</span>.</p>
<p>Let me say that <span class="math-container">$f\colon\mathbb N\to\mathbb N$</span> is a <em>superpolynomial bound</em> if it is time-constructible and <span class="math-container">$f(n)=n^{\omega(1)}$</span>. For example, <span class="math-container">$n^{\log\log\log\log n}$</span> is a superpolynomial bound. In fact, an instructive exercise shows that if <span class="math-container">$g(n)$</span> is any unbounded monotone computable function, there is a superpolynomial bound <span class="math-container">$f$</span> such that <span class="math-container">$f(n)\le n^{g(n)}$</span>.</p>
<p>First, direct diagonalization shows that <span class="math-container">$\Sigma_4^P\nsubseteq\mr{SIZE}(n^k)$</span> for any <span class="math-container">$k$</span>. The same argument gives:</p>
<ul>
<li><p><strong>If <span class="math-container">$f$</span> is any superpolynomial bound, then <span class="math-container">$\Sigma_4\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$</span>.</strong></p>
<p>Proof sketch: For any <span class="math-container">$n$</span>, let <span class="math-container">$C_n$</span> be the lexicographically first circuit of size <span class="math-container">$2f(n)$</span> that computes a Boolean function in <span class="math-container">$n$</span> variables not computable by a circuit of size <span class="math-container">$&lt;f(n)$</span>. Then, the language <span class="math-container">$L$</span> defined by <span class="math-container">$x\in L\iff C_{|x|}(x)=1$</span> works.</p>
</li>
</ul>
<p>A well-known improvement states that <span class="math-container">$S_2\mr P\nsubseteq\mr{SIZE}(n^k)$</span> for any <span class="math-container">$k$</span>. Likewise,</p>
<ul>
<li><p><strong>If <span class="math-container">$f$</span> is any superpolynomial bound, then <span class="math-container">$S_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$</span>.</strong></p>
<p>Proof sketch: If not, then in particular <span class="math-container">$\mr{NP}\subseteq S_2\mr P\subseteq\mr{P/poly}$</span>, hence <span class="math-container">$\mr{PH}=S_2\mr P$</span>. By a padding argument, <span class="math-container">$\Sigma_4\text-\mr{TIME}(f(n))\subseteq S_2\text-\mr{TIME}(f(n))\subseteq\mr{P/poly}$</span>, quod non.</p>
</li>
</ul>
<p>Oblivious classes do even better. Taking into account the objection raised by Apoorva Bhagwat, let <span class="math-container">$\mr{NLin=NTIME}(n)$</span>. Then <span class="math-container">$\mr{NLin}\cup O_2\mr P\nsubseteq\mr{SIZE}(n^k)$</span> for any <span class="math-container">$k$</span>, and the same argument yields:</p>
<ul>
<li><p><strong>If <span class="math-container">$f$</span> is any superpolynomial bound, then <span class="math-container">$\mr{NLin}\cup O_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$</span>.</strong></p>
<p>Proof sketch: If <span class="math-container">$\mr{NLin\subseteq P/poly}$</span>, then by padding, <span class="math-container">$\mr{NP\subseteq P/poly}$</span>, which implies <span class="math-container">$\mr{PH}=O_2\mr P$</span>. Then we proceed as before.</p>
</li>
</ul>
<p>In fact, we do have <span class="math-container">$O_2\mr P\nsubseteq\mr{SIZE}(n^k)$</span> for all <span class="math-container">$k$</span> due to a recent result of <a href="https://eccc.weizmann.ac.il/report/2023/156/" rel="nofollow noreferrer">Li</a>, who proved that there is a single-valued <span class="math-container">$\mr{FS_2P}$</span> algorithm solving the range-avoidance problem (aka dWPHP or sWPHP, as it is known in bounded arithmetic literature). Given an input <span class="math-container">$w\in\{0,1\}^n$</span>, we can apply the range-avoidance algorithm to the function that takes a circuit <span class="math-container">$\{0,1\}^{(k+1)\log n}\to\{0,1\}$</span> of size <span class="math-container">$n^k$</span>, and outputs its truth table; this gives us a Boolean function <span class="math-container">$h\colon\{0,1\}^{(k+1)\log n}\to\{0,1\}$</span> that requires circuit size <span class="math-container">$n^k$</span>, and we apply it to the first <span class="math-container">$(k+1)\log n$</span> bits of <span class="math-container">$w$</span>. This yields an <span class="math-container">$S_2\mr P$</span> language, which is oblivious (i.e., <span class="math-container">$O_2\mr P$</span>) because we only use <span class="math-container">$n$</span> (rather than <span class="math-container">$w$</span>) to find <span class="math-container">$h$</span>.</p>
<p>(Note, by the way, that <span class="math-container">$O_2\mr P\subseteq\mr{P/poly}$</span>.)</p>
<p>Now, pretty much the same argument applied to functions <span class="math-container">$\{0,1\}^{\log f(n)}\to\{0,1\}$</span> shows:</p>
<ul>
<li><strong>If <span class="math-container">$f$</span> is any superpolynomial bound, then <span class="math-container">$O_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$</span>.</strong></li>
</ul>
<p>These arguments are spelled out in <a href="https://eccc.weizmann.ac.il/report/2024/049/" rel="nofollow noreferrer">Gajulapalli, Li &amp; Volkovich</a>.</p>
<p>There are also results involving MA. The often mentioned result that <span class="math-container">$\mr{MA\text-EXP\nsubseteq P/poly}$</span> is an overkill. <a href="https://epubs.siam.org/doi/abs/10.1137/070702680" rel="nofollow noreferrer">Santhanam</a> proved
<span class="math-container">$$\mr{promise\text-MA\cap promise\text-coMA\nsubseteq SIZE}(n^k)$$</span>
for any <span class="math-container">$k$</span>, and a similar argument gives:</p>
<ul>
<li><p><strong>If <span class="math-container">$f$</span> is any superpolynomial bound, then
<span class="math-container">$$\mr{promise\text-MA\text-TIME}(f(n))\cap\mr{promise\text-coMA\text-TIME}(f(n))\nsubseteq\mr{P/poly}.$$</span></strong></p>
<p>Proof sketch: By Santhanam’s Lemma 11 (which is a sharpened version of the standard fact that <span class="math-container">$\mr{PSPACE=IP}$</span> with a PSPACE prover), there is a PSPACE-complete language <span class="math-container">$L$</span> and a randomized poly-time oracle TM <span class="math-container">$M$</span> such that on input <span class="math-container">$x$</span>, <span class="math-container">$M$</span> only asks oracle queries of length <span class="math-container">$|x|$</span>; if <span class="math-container">$x\in L$</span>, then <span class="math-container">$M^L(x)$</span> accepts with probability <span class="math-container">$1$</span>; and if <span class="math-container">$x\notin L$</span>, then for any oracle <span class="math-container">$A$</span>, <span class="math-container">$M^A(x)$</span> accepts with probability <span class="math-container">$\le1/2$</span>.</p>
<p>For a suitable monotone polynomial <span class="math-container">$p$</span>, let <span class="math-container">$A=(A_{\mr{YES}},A_{\mr{NO}})$</span> be the promise problem defined by
<span class="math-container">$$\begin{align}
(x,s)\in A_{\mr{YES}}&amp;\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}}&amp;\iff\forall\text{circuit }C\,\bigl(p(|C|+|x|)\le f(|s|)\to\Pr[M^C(x)\text{ accepts}]\le1/2\bigr).
\end{align}$$</span>
Let <span class="math-container">$h(x)$</span> be a polynomial reduction of <span class="math-container">$L$</span> to its complement, and let <span class="math-container">$B=(B_{\mr{YES}},B_{\mr{NO}})$</span> be the promise problem
<span class="math-container">$$\begin{align}
(x,s)\in B_{\mr{YES}}&amp;\iff(x,s)\in A_{\mr{YES}}\land(h(x),s)\in A_{\mr{NO}},\\
(x,s)\in B_{\rlap{\mr{NO}}\phantom{YES}}&amp;\iff(x,s)\in A_{\mr{NO}}\land(h(x),s)\in A_{\mr{YES}}.
\end{align}$$</span>
If <span class="math-container">$p(n)$</span> is chosen suitably large,
<span class="math-container">$$B\in\mr{promise\text-MA\text-TIME}(f(n))\cap\mr{promise\text-coMA\text-TIME}(f(n)).$$</span>
So, let us assume for contradiction that <span class="math-container">$B$</span> has polynomial-size circuits, say, <span class="math-container">$B\in\mr{SIZE}(n^k)$</span>. Let <span class="math-container">$s(n)$</span> denote the size of the smallest circuit computing <span class="math-container">$L$</span> on inputs of length <span class="math-container">$n$</span>, and put <span class="math-container">$t(n)=f^{-1}(p(s(n)))$</span>; more precisely,
<span class="math-container">$$t(n)=\min\{m:p(s(n))\le f(m)\}.$$</span>
Then <span class="math-container">$x\mapsto(x,1^{t(n)})$</span> is a reduction of <span class="math-container">$L$</span> to <span class="math-container">$B$</span>, thus <span class="math-container">$L\in\mr{SIZE}(t(n)^k)$</span>, which means
<span class="math-container">$$s(n)\le t(n)^k.$$</span>
But since <span class="math-container">$f$</span> is superpolynomial, we have <span class="math-container">$t(n)=s(n)^{o(1)}$</span>. This gives a contradiction for <span class="math-container">$n$</span> sufficiently large.</p>
</li>
</ul>
<p>If we prefer a result with a non-promise version of MA, <a href="https://link.springer.com/chapter/10.1007/3-540-48686-0_21" rel="nofollow noreferrer">Miltersen, Vinodchandran, and Watanabe</a> proved
<span class="math-container">$$\mr{MA\text-TIME}(f(n))\cap\mr{coMA\text-TIME}(f(n))\nsubseteq\mr{P/poly}$$</span>
for a <em>half-exponential</em> function <span class="math-container">$f$</span>. We can improve it in two ways: first, it holds for <span class="math-container">$\tfrac1k$</span>-exponential bounds for any constant <span class="math-container">$k$</span>, and second, it holds for oblivious classes. Here, a <span class="math-container">$\tfrac1k$</span>-exponential function is, roughly speaking, a function <span class="math-container">$f$</span> such that <span class="math-container">$\underbrace{f\circ\dots\circ f}_k=\exp$</span>. See the Miltersen–Vinodchandran–Watanabe paper and references therein for the precise definition; it involves a well-behaved family of well-behaved functions <span class="math-container">$e_\alpha(x)$</span>, <span class="math-container">$\alpha\in\mathbb R_+$</span>, such that <span class="math-container">$e_0(x)=x$</span>, <span class="math-container">$e_1(x)=e^x-1$</span>, and <span class="math-container">$e_{\alpha+\beta}=e_\alpha\circ e_\beta$</span>. Also, if <span class="math-container">$f(n)\le e_\alpha(\mr{poly}(n))$</span> and <span class="math-container">$g(n)\le e_\beta(\mr{poly}(n))$</span>, then <span class="math-container">$f(g(n))\le e_{\alpha+\beta}(\mr{poly}(n))$</span>. Then we have:</p>
<ul>
<li><p><strong><span class="math-container">$\mr{OMA\text-TIME}(e_\alpha)\cap\mr{coOMA\text-TIME}(e_\alpha)\nsubseteq\mr{P/poly}$</span> for any <span class="math-container">$\alpha&gt;0$</span>.</strong></p>
<p>Proof sketch: Assume otherwise. Fix an integer <span class="math-container">$k$</span> such that <span class="math-container">$1/k&lt;\alpha$</span>. Let me abbreviate
<span class="math-container">$$\mr{OcOMT}(f)=\mr{OMA\text-TIME}(\mr{poly}(f(\mr{poly}(n)))\cap\mr{coOMA\text-TIME}(\mr{poly}(f(\mr{poly}(n))).$$</span>
By padding, we have
<span class="math-container">$$\tag{1}\mr{OcOMT}(e_{\beta+1/k})\subseteq\mr{SIZE}(e_\beta(\mr{poly}(n)))$$</span>
for any <span class="math-container">$\beta\ge0$</span>. Moreover, using e.g. Santhanam’s Lemma 11 above, we have the implication
<span class="math-container">$$\tag{2}\mr{PSPACE\subseteq SIZE}(e_\beta(\mr{poly}(n)))\implies\mr{PSPACE\subseteq OcOMT}(e_\beta).$$</span>
Since trivially <span class="math-container">$\mr{PSPACE\subseteq OcOMT}(e_1)$</span>, a repeated application of (1) and (2) shows <span class="math-container">$\mr{PSPACE\subseteq SIZE}(e_{(k-1)/k}(\mr{poly}(n)))$</span>, <span class="math-container">$\mr{PSPACE\subseteq OcOMT}(e_{(k-1)/k})$</span>, <span class="math-container">$\mr{PSPACE\subseteq SIZE}(e_{(k-2)/k}(\mr{poly}(n)))$</span>, <span class="math-container">$\mr{PSPACE\subseteq OcOMT}(e_{(k-2)/k})$</span>, and so on. After <span class="math-container">$k$</span> steps, we reach
<span class="math-container">$$\mr{PSPACE\subseteq P/poly}\qquad\text{and}\qquad\mr{PSPACE=OMA\cap coOMA}.$$</span>
Using padding once more, we get
<span class="math-container">$$\mr{DSPACE}(e_{1/k})\subseteq\mr{OcOMT}(e_{1/k})\subseteq\mr{P/poly},$$</span>
which contradicts the results above, as <span class="math-container">$e_{1/k}$</span> is a superpolynomial bound.</p>
</li>
</ul>

CC BY-SA 4.0
2018-05-10T18:28:18.767Z
2024-06-15T09:20:50.470Z
2024-06-15T09:20:50.470Z
Emil Jeřábek
<p>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.</p>

CC BY-SA 4.0
2024-05-03T11:34:06.763Z
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 (https://eccc.weizmann.ac.il/report/2023/156/).
Emil Jeřábek
CC BY-SA 4.0
2018-05-04T20:15:46.043Z
2018-05-04T20:15:46.043Z
Apoorva Bhagwat
<p>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. </p>

<ol>
<li><p>What is the smallest uniform class C for which one can prove that
C is not contained in P/poly?</p></li>
<li><p>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?</p></li>
</ol>

<p>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. </p>

CC BY-SA 3.0
2016-06-19T22:39:43.037Z
You are essentially asking for a problem with superpolynomial size lower bounds for general circuits.
Kaveh
CC BY-SA 3.0
2016-06-19T22:46:34.630Z
$\mathsf{MA}_\mathrm{exp}$ is known to not be in $\mathsf{P/poly}$. See the [Wikipedia article](https://en.wikipedia.org/wiki/P/poly) for a short proof.
Robin Kothari
CC BY-SA 3.0
2016-06-20T08:11:18.680Z
P/poly is closed under complement, so it contains NEXP if and only if it contains coNEXP.
Emil Jeřábek
CC BY-SA 3.0
2016-06-20T15:15:11.617Z
On the space complexity side: You can also fairly easily show that $\mathsf{DSPACE}[s(n)]$ for any super-polynomial (and space-constructible) $s$ doesn't have polynomial-size circuits. $\mathsf{PSPACE}$ versus $\mathsf{P/poly}$ is of course still open.
Andrew Morgan
CC BY-SA 3.0
2016-06-20T15:35:21.387Z
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?
Springberg
CC BY-SA 3.0
2016-06-20T15:38:16.590Z
@RobinKothari, is $MA_{\mathit{exp}}$ the smallest class known to have a problem not in P/Poly?
Springberg
CC BY-SA 3.0
2016-06-21T18:33:34.820Z
I believe that $MA_{exp}$ is the smallest uniform class with known superpolynomial lower bounds (http://people.cs.uchicago.edu/~fortnow/papers/nonrel.pdf), and that $O^P_2$ is the smallest one with arbitrary polynomial lower bounds (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.6708&rep=rep1&type=pdf).
Alex Golovnev
<circuit-complexity><complexity><advice-and-nonuniformity>
P/Poly vs Uniform Complexity Classes
Springberg
# P/Poly vs Uniform Complexity Classes

(Asked by: username_0 on 2016-06-19)

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.

**Tags:** circuit-complexity, complexity, advice-and-nonuniformity

> **Comments:**
> **username_1**: You are essentially asking for a problem with superpolynomial size lower bounds for general circuits.  
> **username_2**: $\mathsf{MA}_\mathrm{exp}$ is known to not be in $\mathsf{P/poly}$. See the [Wikipedia article](https://en.wikipedia.org/wiki/P/poly) for a short proof.  
> **username_3**: P/poly is closed under complement, so it contains NEXP if and only if it contains coNEXP.  
> **username_4**: On the space complexity side: You can also fairly easily show that $\mathsf{DSPACE}[s(n)]$ for any super-polynomial (and space-constructible) $s$ doesn't have polynomial-size circuits. $\mathsf{PSPACE}$ versus $\mathsf{P/poly}$ is of course still open.  
> **username_0**: 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?  
> **username_0**: @RobinKothari, is $MA_{\mathit{exp}}$ the smallest class known to have a problem not in P/Poly?  
> **username_5**: I believe that $MA_{exp}$ is the smallest uniform class with known superpolynomial lower bounds (http://people.cs.uchicago.edu/~fortnow/papers/nonrel.pdf), and that $O^P_2$ is the smallest one with arbitrary polynomial lower bounds (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.6708&rep=rep1&type=pdf).  

---

## 3 answers

### Answer by username_0 on 2016-07-20. Score: 4 | Accepted answer

Since nobody posted an answer, I will answer the question myself with the comments posted in the original question. Thanks to username_2, Emil Jerabek, username_4 and username_5.

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


---

### Answer by username_3 on 2018-05-10. Score: 13

$\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 username_6, 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](https://eccc.weizmann.ac.il/report/2023/156/), 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](https://eccc.weizmann.ac.il/report/2024/049/).

There are also results involving MA. The often mentioned result that $\mr{MA\text-EXP\nsubseteq P/poly}$ is an overkill. [Santhanam](https://epubs.siam.org/doi/abs/10.1137/070702680) 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](https://link.springer.com/chapter/10.1007/3-540-48686-0_21) 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.


---

### Answer by username_6 on 2018-05-04. Score: 5

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.

> **Comments:**
> **username_3**: 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 (https://eccc.weizmann.ac.il/report/2023/156/).  

---

