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

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

<blockquote>
  <p><strong>Problem:</strong>
  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}$$</p>
  
  <p>$$\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?</p>
</blockquote>

<p>$(1)$ should be true since technically any circuit produced by a deterministic turing machine can also be assumed to be part of <em>non-uniform</em> 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 <em>uniformity</em> and <em>non-uniformity</em> makes it unclear.</p>

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

<p><strong>Update:</strong> Michael Cadilhac points that this problem is similar to asking whether <em>extensionally uniform</em> classes are contained in <em>intentionally uniform</em> ones where <em>extensionally uniform</em> is given in McKenzie's work <a href="http://arxiv.org/abs/0805.4072" rel="nofollow">http://arxiv.org/abs/0805.4072</a>? 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.</p>

CC BY-SA 3.0
2016-01-01T10:46:36.440Z
Why did you delete your previous question?
Michaël Cadilhac
CC BY-SA 3.0
2016-01-01T10:54:05.743Z
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?"
Michaël Cadilhac
CC BY-SA 3.0
2016-01-01T14:29:04.987Z
@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)
Turbo
CC BY-SA 3.0
2016-01-03T10:57:43.957Z
For 2 see [this](http://cstheory.stackexchange.com/q/1982/).
Kaveh
CC BY-SA 3.0
2016-01-03T15:18:30.087Z
@Kaveh thank you
Turbo
CC BY-SA 3.0
2016-01-03T15:37:39.290Z
@kaveh but there could be a much smaller intersecting class than NP?
Turbo
CC BY-SA 3.0
2016-01-03T15:50:56.740Z
@Kaveh 1 also seems open ended from your post there.
Turbo
<complexity-classes><circuit-complexity><advice-and-nonuniformity><hierarchy-theorems><uniformity>
Interlaced uniform versus non-uniform hierarchy
Turbo
# Interlaced uniform versus non-uniform hierarchy

(Asked by: username_0 on 2016-01-01)

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.

**Tags:** complexity-classes, circuit-complexity, advice-and-nonuniformity, hierarchy-theorems, uniformity

> **Comments:**
> **username_1**: Why did you delete your previous question?  
> **username_1**: 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?"  
> **username_0**: @username_2 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)  
> **username_2**: For 2 see [this](http://cstheory.stackexchange.com/q/1982/).  
> **username_0**: @username_2 thank you  
> **username_0**: @kaveh but there could be a much smaller intersecting class than NP?  
> **username_0**: @username_2 1 also seems open ended from your post there.  

---

## 0 answers

