Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
@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
add comment

1 Answer

up vote 5 down vote accepted

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.
share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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