12
$\begingroup$

I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”.

On the bottom of page 2 they remark that the results of Kannan imply that $NEXPTIME^{NP}$ does not have polynomial size circuits. I know that in the exponential time hierarchy, $NEXPTIME^{NP}$ is just $\Sigma_2EXP$, and I also know that Kannan's result is that $\forall c\mbox{ }\exists L\in\Sigma_2P$ such that $L \not\in Size(n^c)$. Of course, Kannan's theorem is NOT saying $\Sigma_2P \not\subset P/poly$ (in order for that to be the case we would need to show that $\exists L\in\Sigma_2P$ such that $\forall c$, $L \not\in Size(n^c)$. However, I don't see how Kannan's result implies that $NEXPTIME^{NP} \not\subset P/poly$?

$\endgroup$

migrated from cs.stackexchange.com Apr 18 '14 at 15:13

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ Perhaps that's more appropriate for cstheory.se. $\endgroup$ – Yuval Filmus Apr 18 '14 at 14:11
  • $\begingroup$ @YuvalFilmus Ok, thanks. If a moderator thinks it is more appropriate for cstheory.se, then feel free to move it. $\endgroup$ – Lorraine Apr 18 '14 at 14:12
  • 8
    $\begingroup$ This is also presently on the cs354 problem set... :-/ ... I explicitly instructed students not to ask the internet, so "Lorraine" better hope they are not taking my class. $\endgroup$ – Ryan Williams Apr 18 '14 at 20:59
  • 4
    $\begingroup$ @Sasho, I think it would be good to do so, at least until after the due date of the assignment. $\endgroup$ – Kaveh Apr 19 '14 at 5:04
  • 3
    $\begingroup$ @Turbo I guess I might as well, hopefully this is not on someone else's problem set at the moment. $\endgroup$ – Sasho Nikolov Dec 11 '17 at 2:22
11
$\begingroup$

This version of the answer incorporates feedback from Emil Jeřábek.

As far as I can see, the main twist is that there is a language in $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ of exponential circuit complexity. In particular, fix a binary encoding of boolean circuits and define $L$ as the language defined by

$L_n$ is not decided by any circuit of size $2^{n/2}$, and

any language $L'_n \subseteq \{0,1\}^n$ which precedes $L_n$ lexicographically is decided by some circuit $C$ of size at most $2^{n/2}$,

where the notation $L_n$ means the slice $L_n = L \cap \{0,1\}^n$.

To do this in exponential time with a $\Sigma_2^\mathsf{P}$ oracle, you can use binary search over subsets of $\{0,1\}^n$ (think of them as $2^n$ bit integers) to find the first such set which has circuit complexity $> 2^{n/2}$. You just keep the current guess of $L_n$, and use the oracle to test if there exists a $L'_n \prec_{\text{lex}} L_n$ of circuit complexity at least $2^{n/2}$. Since this gives a machine in $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ which writes down the whole slice $L_n$, clearly we can also decide membership in $L_n$, and, therefore, in $L$.

This is very much as in Kannan's argument, but scaled up and streamlined to use the exponential time. Then you should be able to use a scaled-up version of the Karp-Lipton theorem to show that if $\mathsf{NEXP} \subseteq \mathsf{P/poly}$, then $\mathsf{EXP}^{\Sigma^\mathsf{P}_2} \subseteq \mathsf{NEXP}^{\mathsf{NP}}$, and you can carry out the case analysis in Kannan's proof.

$\endgroup$
  • $\begingroup$ AFAICS your description gives directly an $\mathrm{EXP}^{\Sigma^P_2}$ language, rather than $\mathrm{NEXP}^{\Sigma^P_3}$. $\endgroup$ – Emil Jeřábek Dec 11 '17 at 9:21
  • $\begingroup$ @EmilJeřábek My brain was never able to process oracle machines. I quantifier depth four: $w \in \{0,1\}^n$ is in $L$ if there exists a circuit $C^*$ of size $\le 2^n$ such that $C^*(w) = 1$ and [ for all circuits $C$ of size $2^{n/2}$ there exists a word $w' \in \{0,1\}^n$ for which $C(w') \neq C(w)$ ] and [ for all $C'$ which precede $C^*$ in lex order there exists a circuit $C''$ of size at most $2^{n/2}$ s.t. for all $w' \in \{0,1\}^n$ $C'(w') = C''(w')$ ]. This seems to be the fourth level of the exponential hierarchy. What is it in oracle notation? $\endgroup$ – Sasho Nikolov Dec 11 '17 at 23:22
  • 2
    $\begingroup$ First, "there exists a word..." and the similar universal quantifier near the end do not count as they are linear size, hence they can be computed deterministically in exponential time. Second, the outermost quantifier can be simulated deterministically in exponential time using binary search. $\endgroup$ – Emil Jeřábek Dec 12 '17 at 9:58
  • 1
    $\begingroup$ That is, the lexicographically first Boolean function $f$ on $n$ inputs that does not have circuits of size $2^{n/2}$ can be found by exponential-time binary search with oracle for the predicate "there exists a function $f'$ lexicographically preceding $f$ that is not computable by a circuit of size $2^{n/2}$". $\endgroup$ – Emil Jeřábek Dec 12 '17 at 10:06
  • 1
    $\begingroup$ @SashoNikolov So it still works since $EXP^{\Sigma_2^P}\subseteq NEXP^{\Sigma_3^P}$. However we cannot use if $NEXP\subseteq i.o.P/poly$ then apply Karp-Lipton in cstheory.stackexchange.com/questions/39837/…. So we have $EXP^{PP}\not\subseteq i.o.P/poly$ and $NEXP^{\Sigma_3^P}\not\subseteq i.o.P/poly$. This does not work for $NEXP^{NP}$. $\endgroup$ – Turbo Dec 22 '17 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy