9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You are essentially asking for a problem with superpolynomial size lower bounds for general circuits. $\endgroup$ – Kaveh Jun 19 '16 at 22:39
  • 8
    $\begingroup$ $\mathsf{MA}_\mathrm{exp}$ is known to not be in $\mathsf{P/poly}$. See the Wikipedia article for a short proof. $\endgroup$ – Robin Kothari Jun 19 '16 at 22:46
  • 4
    $\begingroup$ P/poly is closed under complement, so it contains NEXP if and only if it contains coNEXP. $\endgroup$ – Emil Jeřábek supports Monica Jun 20 '16 at 8:11
  • 2
    $\begingroup$ 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? $\endgroup$ – Springberg Jun 20 '16 at 15:35
  • 2
    $\begingroup$ 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/…). $\endgroup$ – Alex Golovnev Jun 21 '16 at 18:33
6
$\begingroup$

$\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 $<f(n)$. 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.

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

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