<blockquote>
<ol>
<li><p>Is <span class="math-container">$NEXP^{NP}\not\subseteq i.o.P/poly$</span>?</p>
</li>
<li><p>Is there any consequence if <span class="math-container">$NP$</span> or <span class="math-container">$PP$</span> is in <span class="math-container">$i.o.P/poly$</span>?</p>
</li>
</ol>
</blockquote>
<p>Showing <span class="math-container">$NEXP^{NP}\not\subseteq P/poly$</span> needs Karp-Lipton.</p>
<p><s>What is the best <span class="math-container">$i.o.P/poly$</span> lower bound result we know</s>? As of this writing this is <span class="math-container">$EXP^{\Sigma_2P}\not\subseteq i.o.P/poly$</span>.</p>

CC BY-SA 3.0
2017-12-22T13:07:46.797Z
Doesn't EXPSPACE contain this function https://cstheory.stackexchange.com/a/22183/4896, whose intersection with $\{0,1\}^n$ has circuit complexity $2^{n/2}$ for *every* $n$?
Sasho Nikolov
CC BY-SA 3.0
2017-12-22T13:27:00.950Z
My understanding is a class could not be in $P/poly$ but could be in $i.o.P/poly$ (actually I was interested $NEXP^{NP}$ and $EXP^{PP}$).
Turbo
CC BY-SA 3.0
2017-12-22T14:11:59.237Z
You should really ask the questions you are interested in then.
Sasho Nikolov
CC BY-SA 3.0
2017-12-22T14:22:37.047Z
For your modified question: isn't the exponential time hierarchy contained in EXP$^{PP}$ by a scaled up version of Toda's theorem? And wouldn't that answer your question for the same reason that I pointed out above?
Sasho Nikolov
CC BY-SA 3.0
2017-12-22T15:32:42.817Z
Wait, what is the "standard proof" that NEXP^NP is not in P/poly? It is not known if PH collapses assuming NP is in io-P/poly... so I don't see how you get an a.e. lower bound easily, since the usual proof uses Karp-Lipton. See for example Fortnow and Santhanam's "Robust Simulations and Significant Separations" for a discussion. You can get EXP^(Sigma2 P) not in io-P/poly, because that can be proved with a direct diagonalization on each input length.
Ryan Williams
CC BY-SA 3.0
2017-12-22T16:04:42.893Z
@RyanWilliams That is correct there is no Karp-Lipton in that case. Could you elaborate on the $EXP^{\Sigma_2^P}$ lower bound?
Turbo
CC BY-SA 3.0
2017-12-22T16:40:54.153Z
See for example Miltersen Vinodchandran and Watanabe 99
Ryan Williams
CC BY-SA 3.0
2017-12-22T17:08:29.523Z
EXP$^{\Sigma_2^P}$ contains the language in the answer I linked in my first comment: see Emil's comments under the answer. That language is designed to have exponential circuit complexity for all $n$. If EXP$^{PP}$ indeed contains the exponential hierarchy, then it will contain EXP$^{\Sigma_2^P}$, and the same language.
Sasho Nikolov
<cc.complexity-theory><circuit-complexity>
On $i.o.P/poly$?
Turbo
# On $i.o.P/poly$?

(Asked by: username_0 on 2017-12-22)

> 1. Is $NEXP^{NP}\not\subseteq i.o.P/poly$?
> 2. Is there any consequence if $NP$ or $PP$ is in $i.o.P/poly$?

Showing $NEXP^{NP}\not\subseteq P/poly$ needs Karp-Lipton.

~~What is the best $i.o.P/poly$ lower bound result we know~~? As of this writing this is $EXP^{\Sigma\_2P}\not\subseteq i.o.P/poly$.

**Tags:** cc.complexity-theory, circuit-complexity
> **Comments:**
> **username_1**: Doesn't EXPSPACE contain this function https://cstheory.stackexchange.com/a/22183/4896, whose intersection with $\{0,1\}^n$ has circuit complexity $2^{n/2}$ for *every* $n$?  
> **username_0**: My understanding is a class could not be in $P/poly$ but could be in $i.o.P/poly$ (actually I was interested $NEXP^{NP}$ and $EXP^{PP}$).  
> **username_1**: You should really ask the questions you are interested in then.  
> **username_1**: For your modified question: isn't the exponential time hierarchy contained in EXP$^{PP}$ by a scaled up version of Toda's theorem? And wouldn't that answer your question for the same reason that I pointed out above?  
> **username_2**: Wait, what is the "standard proof" that NEXP^NP is not in P/poly? It is not known if PH collapses assuming NP is in io-P/poly... so I don't see how you get an a.e. lower bound easily, since the usual proof uses Karp-Lipton. See for example Fortnow and Santhanam's "Robust Simulations and Significant Separations" for a discussion. You can get EXP^(Sigma2 P) not in io-P/poly, because that can be proved with a direct diagonalization on each input length.  
> **username_0**: @RyanWilliams That is correct there is no Karp-Lipton in that case. Could you elaborate on the $EXP^{\Sigma_2^P}$ lower bound?  
> **username_2**: See for example Miltersen Vinodchandran and Watanabe 99  
> **username_1**: EXP$^{\Sigma_2^P}$ contains the language in the answer I linked in my first comment: see Emil's comments under the answer. That language is designed to have exponential circuit complexity for all $n$. If EXP$^{PP}$ indeed contains the exponential hierarchy, then it will contain EXP$^{\Sigma_2^P}$, and the same language.  

---

## 0 answers

