# Separation of classes with different amounts of advice?

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.

-
@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 Nov 19 '10 at 20:16
Sorry, did the rollback because the typeset math looked a bit hard to read, but thanks for the tag. –  matt hastings Nov 19 '10 at 20:23
@Sadeq: I added the tags [advice] and [separation] without realizing the history. Thanks for the note! –  Tsuyoshi Ito Nov 19 '10 at 20:26

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.

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:

-
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 Nov 19 '10 at 20:25
@matt: See if the edited answer fits what you need. –  Sadeq Dousti Nov 19 '10 at 20:52
That's the sort of thing I am looking for, thanks. –  matt hastings Nov 19 '10 at 22:21