2
$\begingroup$

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?
$\endgroup$
3
$\begingroup$
  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)$.)

  1. 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}}$.
$\endgroup$
  • 1
    $\begingroup$ As far as I can tell, circuits $C$ of size $f(n)$ need $\: j\cdot f(n) \cdot \log(\hspace{.04 in}f(n)) \:$ bits to represent them, $\hspace{.82 in}$ where the constant $j$ depends on the precise gates allowed. ​ ​ $\endgroup$ – user6973 Nov 15 '17 at 12:39
  • $\begingroup$ All right, that’s a good point. $\endgroup$ – Emil Jeřábek Nov 15 '17 at 15:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.