<ol>
<li>For any space-constructible function $f$ such that $f(n)=\omega(n)$, we have $\mathrm{NSPACE}(f(n)\log n)\nsubseteq\mathrm{SIZE}(n)$. This follows by simple brute force: you can compute the predicate</li>
</ol>

<blockquote>
  <p>$\exists$ a truth-table $t$ of a Boolean function in $O(\log f(n))$ variables such that ($\forall$ circuit $C$ of size $f(n)$, $C$ does not compute $t$) and ($\forall$ truth-tables $t'$ lexicographically smaller than $t$, $\exists$ a circuit of size $O(f(n))$ that computes $t'$) and $t(x)=1$</p>
</blockquote>

<p>(where $x$ is the given input of length $n$) on an alternating TM with space $O(f(n)\log n)$ and $O(1)$ alternations, hence in $\mathrm{NSPACE}(O(f(n)\log n))$ by the Immerman–Szelepcsényi theorem. (The $\log n$ factor comes from the fact that a description of a circuit of size $f(n)$ takes $O(f(n)\log f(n))$ bits; we may assume $f(n)\le n^2$, thus $\log f(n)=O(\log n)$.)</p>

<ol start="2">
<li>The same kind of argument shows that $\mathrm{TIME}(n^{f(n)})^\mathrm{NP}\nsubseteq\mathrm{SIZE}(n)$ for any function $f(n)$ as above. However, this is really overkill. For example, it is known that oblivious $S_2^\mathrm P$ is also not contained in $\mathrm{SIZE}(n)$ (or $\mathrm{SIZE}(n^k)$ for any fixed $k$, for that matter), and it sits fairly low in the polynomial-time hierarchy, hence it is “almost” a much smaller class than $\mathrm{E^{NP}}$.</li>
</ol>

CC BY-SA 3.0
2017-11-15T15:43:23.947Z
All right, that’s a good point.
Emil Jeřábek
CC BY-SA 3.0
2017-11-15T10:44:39.397Z
2017-11-15T15:49:00.887Z
2017-11-15T15:49:00.887Z
Emil Jeřábek
<p>If I'm not mistaken it is not known whether $E^{NP} \subseteq {\rm SIZE}(n)$
where $E^{NP}$ is the class of problems solvable by a TM which works in time $2^{O(n)}$ and is allowed to make queries of size $2^{O(n)}$ to an NP oracle, and ${\rm SIZE(n)}$ is the class of functions solvable by non-uniform circuits of size $O(n)$. </p>

<p>Since ${\rm NSPACE}[n]\subseteq E \subseteq E^{NP}$ the above observation implies that the question of whether ${\rm NSPACE}[n]\subseteq {\rm SIZE}[n]$ is open. </p>

<p><strong>Questions:</strong></p>

<ol>
<li>What is the smallest function $f(n)$ such that it is known
unconditionally  that ${\rm NSPACE}[f(n)]\nsubseteq {\rm SIZE}[n]$?</li>
<li>What is the smallest class $\mathcal{C}$ containing $E^{NP}$ such that it is known unconditionally that $\mathcal{C}\nsubseteq SIZE[n]$? </li>
<li>What is a good reference for relations between uniform and non-uniform circuit classes? </li>
</ol>

<circuit-complexity><lower-bounds><advice-and-nonuniformity>
Non-Uniform Lower Bounds for NSPACE
verifying
# Non-Uniform Lower Bounds for NSPACE

(Asked by: username_0 on 2017-11-14)

If I'm not mistaken it is not known whether $E^{NP} \subseteq {\rm SIZE}(n)$
where $E^{NP}$ is the class of problems solvable by a TM which works in time $2^{O(n)}$ and is allowed to make queries of size $2^{O(n)}$ to an NP oracle, and ${\rm SIZE(n)}$ is the class of functions solvable by non-uniform circuits of size $O(n)$.

Since ${\rm NSPACE}[n]\subseteq E \subseteq E^{NP}$ the above observation implies that the question of whether ${\rm NSPACE}[n]\subseteq {\rm SIZE}[n]$ is open.

**Questions:**

1. What is the smallest function $f(n)$ such that it is known
   unconditionally that ${\rm NSPACE}[f(n)]\nsubseteq {\rm SIZE}[n]$?
2. What is the smallest class $\mathcal{C}$ containing $E^{NP}$ such that it is known unconditionally that $\mathcal{C}\nsubseteq SIZE[n]$?
3. What is a good reference for relations between uniform and non-uniform circuit classes?

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

---

## 1 answers

### Answer by username_1 on 2017-11-15. Score: 3

1. For any space-constructible function $f$ such that $f(n)=\omega(n)$, we have $\mathrm{NSPACE}(f(n)\log n)\nsubseteq\mathrm{SIZE}(n)$. This follows by simple brute force: you can compute the predicate

> $\exists$ a truth-table $t$ of a Boolean function in $O(\log f(n))$ variables such that ($\forall$ circuit $C$ of size $f(n)$, $C$ does not compute $t$) and ($\forall$ truth-tables $t'$ lexicographically smaller than $t$, $\exists$ a circuit of size $O(f(n))$ that computes $t'$) and $t(x)=1$

(where $x$ is the given input of length $n$) on an alternating TM with space $O(f(n)\log n)$ and $O(1)$ alternations, hence in $\mathrm{NSPACE}(O(f(n)\log n))$ by the Immerman–Szelepcsényi theorem. (The $\log n$ factor comes from the fact that a description of a circuit of size $f(n)$ takes $O(f(n)\log f(n))$ bits; we may assume $f(n)\le n^2$, thus $\log f(n)=O(\log n)$.)

2. The same kind of argument shows that $\mathrm{TIME}(n^{f(n)})^\mathrm{NP}\nsubseteq\mathrm{SIZE}(n)$ for any function $f(n)$ as above. However, this is really overkill. For example, it is known that oblivious $S\_2^\mathrm P$ is also not contained in $\mathrm{SIZE}(n)$ (or $\mathrm{SIZE}(n^k)$ for any fixed $k$, for that matter), and it sits fairly low in the polynomial-time hierarchy, hence it is “almost” a much smaller class than $\mathrm{E^{NP}}$.

> **Comments:**
> **username_1**: All right, that’s a good point.  

---

