<p>Let $s(n) \ge n$ be some function. It can be proven that:</p>

<p>$\mathbf{DSIZE}(s) \subseteq \mathbf{DTIME}(s^2) / F(O(s\log s))$
</p>

<p>Here, $\mathbf{DSIZE}(s)$ denotes the set of languages decidable by deterministic circuits of size $s$. The notation $\mathbf{K/F}$ denotes the complexity class $\mathbf{K}$ with advice function from the set $\mathbf{F}$, defined as:</p>

<p>$F(f) = \left\{h \colon \{0,1\}^* \to \{0,1\}^* \mid |h(x)| \le f(|x|) \text{ for all } x\right\}$.</p>

<p>In addition, let $d(n) \ge \log n$ be another function. Then:</p>

<p>$\mathbf{DDEPTH}(d) \subseteq \mathbf{DSPACE}(d) / F(2^{O(d)})$
</p>

<p>where $\mathbf{DDEPTH}(d)$ denotes the set of languages decidable by deterministic circuits of depth $d$.</p>

<hr>

<p><strong>Edit:</strong> two more inclusions:</p>

<p>For $t(n) \ge n$ we have $\mathbf{DTIME}(t) \subseteq \mathbf{DSIZE}(t \log t)$,
and for $l(n) \ge \log n$ we have $\mathbf{NSPACE}(l) \subseteq \mathbf{DDEPTH}(l^2)$.</p>

<hr>

<blockquote>
  <p>For proofs, see section 2-3 of <a href="http://rads.stackoverflow.com/amzn/click/3642083986" rel="nofollow">Heribert Vollmer's book</a>.</p>
</blockquote>

<p>Using these inclusions, and time/space hierarchies, one can build hierarchies for non-uniform complexity classes.</p>

<hr>

<h3>Edit 2:</h3>

<p>You may combine the above results with the following results on hierarchies for classes with advice:</p>

<ol>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.6786&amp;rep=rep1&amp;type=pdf" rel="nofollow">Time Hierarchies for Computations with a Bit of Advice</a>.</li>
<li><a href="http://www.cs.uchicago.edu/~fortnow/papers/advice.pdf" rel="nofollow">Unconditional Lower Bounds Against Advice</a>.</li>
</ol>

CC BY-SA 2.5
2010-11-19T20:25:35.750Z
Not sure this answers the question.  It puts circuits in languages with advices (which I was implicitly doing and is fairly clear why it is true), but doesn't (unless I'm missing something?) answer the question about how to get the separation?  I mean, you mention time/space hierarchies, but then what are the known hierarchies for classes with advice?
matt hastings
CC BY-SA 2.5
2010-11-19T20:52:37.997Z
@matt: See if the edited answer fits what you need.
Sadeq Dousti
CC BY-SA 2.5
2010-11-19T22:21:19.443Z
That's the sort of thing I am looking for, thanks.
matt hastings
CC BY-SA 2.5
2010-11-19T19:53:03.827Z
2010-11-19T20:51:56.903Z
2010-11-19T20:51:56.903Z
Sadeq Dousti
<p>The time hierarchy theorem lets one show that, for example, there are problems in P that cannot be solved in time less than const*n^2 by a Turing machine.  But give the Turing machine some advice and all bets are off.  One can't yet show that even a linear size circuit can't solve all of PSPACE.  So, what if we try to compare two different classes in which both have advice?  For example, can one separate polynomial space with logarithmic advice from linear time with linear advice?  That's just a made-up example question, I am wondering what general results there are along these lines.</p>

CC BY-SA 2.5
2010-11-19T20:16:57.793Z
@Tsuyoshi: I added the `[advice]` tag, and made a few changes (like typesetting math), but the OP rolled back my changes! Thanks for adding the correct tags again.
Sadeq Dousti
CC BY-SA 2.5
2010-11-19T20:23:37.250Z
Sorry, did the rollback because the typeset math looked a bit hard to read, but thanks for the tag.
matt hastings
CC BY-SA 2.5
2010-11-19T20:26:10.083Z
@Sadeq: I added the tags [advice] and [separation] without realizing the history.  Thanks for the note!
Tsuyoshi Ito
<cc.complexity-theory><lower-bounds><circuit-complexity><advice-and-nonuniformity><separation>
Separation of classes with different amounts of advice?
matt hastings
# Separation of classes with different amounts of advice?

(Asked by: username_0 on 2010-11-19)

The time hierarchy theorem lets one show that, for example, there are problems in P that cannot be solved in time less than const\*n^2 by a Turing machine. But give the Turing machine some advice and all bets are off. One can't yet show that even a linear size circuit can't solve all of PSPACE. So, what if we try to compare two different classes in which both have advice? For example, can one separate polynomial space with logarithmic advice from linear time with linear advice? That's just a made-up example question, I am wondering what general results there are along these lines.

**Tags:** cc.complexity-theory, lower-bounds, circuit-complexity, advice-and-nonuniformity, separation
> **Comments:**
> **username_1**: @Tsuyoshi: I added the `[advice]` tag, and made a few changes (like typesetting math), but the OP rolled back my changes! Thanks for adding the correct tags again.  
> **username_0**: Sorry, did the rollback because the typeset math looked a bit hard to read, but thanks for the tag.  
> **username_2**: @Sadeq: I added the tags [advice] and [separation] without realizing the history.  Thanks for the note!  

---

## 1 answers

### Answer by username_1 on 2010-11-19. Score: 5 | Accepted answer

Let $s(n) \ge n$ be some function. It can be proven that:

$\mathbf{DSIZE}(s) \subseteq \mathbf{DTIME}(s^2) / F(O(s\log s))$

Here, $\mathbf{DSIZE}(s)$ denotes the set of languages decidable by deterministic circuits of size $s$. The notation $\mathbf{K/F}$ denotes the complexity class $\mathbf{K}$ with advice function from the set $\mathbf{F}$, defined as:

$F(f) = \left\{h \colon \{0,1\}^\* \to \{0,1\}^\* \mid |h(x)| \le f(|x|) \text{ for all } x\right\}$.

In addition, let $d(n) \ge \log n$ be another function. Then:

$\mathbf{DDEPTH}(d) \subseteq \mathbf{DSPACE}(d) / F(2^{O(d)})$

where $\mathbf{DDEPTH}(d)$ denotes the set of languages decidable by deterministic circuits of depth $d$.

---

**Edit:** two more inclusions:

For $t(n) \ge n$ we have $\mathbf{DTIME}(t) \subseteq \mathbf{DSIZE}(t \log t)$,
and for $l(n) \ge \log n$ we have $\mathbf{NSPACE}(l) \subseteq \mathbf{DDEPTH}(l^2)$.

---

> For proofs, see section 2-3 of [Heribert Vollmer's book](http://rads.stackoverflow.com/amzn/click/3642083986).

Using these inclusions, and time/space hierarchies, one can build hierarchies for non-uniform complexity classes.

---

### Edit 2:

You may combine the above results with the following results on hierarchies for classes with advice:

1. [Time Hierarchies for Computations with a Bit of Advice](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.6786&rep=rep1&type=pdf).
2. [Unconditional Lower Bounds Against Advice](http://www.cs.uchicago.edu/~fortnow/papers/advice.pdf).

> **Comments:**
> **username_0**: Not sure this answers the question.  It puts circuits in languages with advices (which I was implicitly doing and is fairly clear why it is true), but doesn't (unless I'm missing something?) answer the question about how to get the separation?  I mean, you mention time/space hierarchies, but then what are the known hierarchies for classes with advice?  
> **username_1**: @matt: See if the edited answer fits what you need.  
> **username_0**: That's the sort of thing I am looking for, thanks.  

---

