1

Denote $\mathsf{uniform}$ class with prefix $\mathsf{u}$ and $\mathsf{non}$-$\mathsf{uniform}$ class with prefix $\mathsf{nu}$.

In following some non-trivial standard notion of uniformity (like $\mathsf{DLOGTIME}$-$\mathsf{uniform}$) is assumed.

Problem: Does $$\mathsf{uTC}^i\mbox{ }{{{\underbrace{\subseteq}_{(1)}}\mbox{ }\mathsf{nuTC}^{i+k_i}\cap\mathcal C_{i}\subseteq}\mbox{ }}\mathcal C_{i}\subseteq\mbox{ }\mathcal C_{i+k_i}$$

$$\mathsf{nuTC}^{i}\cap\mathcal C_{i+l_i}\mbox{ }{\underbrace{\subseteq}_{(2)}}\mbox{ }\mathsf{uTC}^{i+l_i}\subseteq\mathcal C_{i+l_i}$$ hold at any $i\in\Bbb N\cup\{0\}$ for some $k_i\in\Bbb N\cup\{0\}$ and some $l_i\in\Bbb N$ for any choice of complexity class $\mathcal C_{j}$ such that $\mathsf{uTC}^{j}\subseteq\mathcal C_{j}\subseteq\mathsf{EXPSPACE}$ holds?

$(1)$ should be true since technically any circuit produced by a deterministic turing machine can also be assumed to be part of non-uniform model and so $\mathsf{uTC}^{i}\subseteq\mbox{ }{\mbox{ }\mathsf{nuTC}^{i+k_i}\cap\mathcal C_{i}\subseteq\mbox{ }}\mathcal C_{i}$ should hold even with $k_i=0$ but again uniformity and non-uniformity makes it unclear.

It seems pretty trivial that $(2)$ should hold since greater depth circuits should be more expressive however uniformity puts a restriction on type of circuits that can be generated at depth $i+l_i$.

Update: Michael Cadilhac points that this problem is similar to asking whether extensionally uniform classes are contained in intentionally uniform ones where extensionally uniform is given in McKenzie's work http://arxiv.org/abs/0805.4072? If we go by analogy from there McKenzie's classes under consideration $\mathcal C_{i}$ would be much smaller than $\mathsf{uTC}^i$ when taken in context here and not applicable to current problem.

Turbo
  • 12,812
  • 1
  • 19
  • 68

0 Answers0