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.

  • 1
    $\begingroup$ Why did you delete your previous question? $\endgroup$ Jan 1, 2016 at 10:46
  • $\begingroup$ I cannot see why you did not just edit your previous question. That seems completely overkill, especially since we had a conversation going with some other user (I couldn't see the name as the post was deleted). In any case, you should probably point to the fact that you ask: "Are extensionally uniform classes in intentionally uniform ones?" $\endgroup$ Jan 1, 2016 at 10:54
  • $\begingroup$ @Kaveh I observed that it seems to provide some kind of direct connection between uniform model and non-uniform models (if one is hard the should be hard if above post holds true) $\endgroup$
    – Turbo
    Jan 1, 2016 at 14:29
  • 1
    $\begingroup$ For 2 see this. $\endgroup$
    – Kaveh
    Jan 3, 2016 at 10:57
  • $\begingroup$ @Kaveh thank you $\endgroup$
    – Turbo
    Jan 3, 2016 at 15:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.