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.

  • $\begingroup$ @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. $\endgroup$ Commented Nov 19, 2010 at 20:16
  • $\begingroup$ Sorry, did the rollback because the typeset math looked a bit hard to read, but thanks for the tag. $\endgroup$ Commented Nov 19, 2010 at 20:23
  • $\begingroup$ @Sadeq: I added the tags [advice] and [separation] without realizing the history. Thanks for the note! $\endgroup$ Commented Nov 19, 2010 at 20:26

1 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.
  • $\begingroup$ 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? $\endgroup$ Commented Nov 19, 2010 at 20:25
  • $\begingroup$ @matt: See if the edited answer fits what you need. $\endgroup$ Commented Nov 19, 2010 at 20:52
  • $\begingroup$ That's the sort of thing I am looking for, thanks. $\endgroup$ Commented Nov 19, 2010 at 22:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.