Separation of classes with different amounts of advice?

Question

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.

Answer 1

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:

1. Time Hierarchies for Computations with a Bit of Advice.
2. Unconditional Lower Bounds Against Advice.