<p>Any separation of classes closed under "polynomial resources" has an oracle making them equal. (This is provided the oracle mechanism is fair and allows both machine models to make polynomial length queries and no more.)</p>

<p>Let $TC0^{O}$ be "$TC0$ with gates for oracle $O$". Letting $O$ be a $PSPACE$-complete language under $TC0$ reductions, we have $TC0^{O} = PSPACE = PSPACE^{O} = PP^{O}$, where  in the oracle mechanism for $PSPACE$, we count the space usage of the oracle tape along with the rest of the memory. (So only polynomially length queries are asked.) Such an equality holds for many classes "closed under polynomial resources", in the sense that they can ask polynomially length queries to an oracle, but no larger. These classes include stuff like $AC0$, $TC0$, $LOGSPACE$ (under a different oracle mechanism which does not count oracle queries towards the space bound), $P$, $NP$, $PH$, and $PP$. So any separation of classes in this list must necessarily use some kind of "non-relativizing" argument. This also implies (for example) that the natural proofs of things like Parity not in $AC0$ are non-relativizing (but this is even easier: all you need here is an oracle for parity, so you get $AC0[2]$).</p>

<p>In the collection of proofs you cite, I believe most of them (if not all) work by assuming $TC0 = PP$ and deriving a contradiction. These kinds of results are called "indirect diagonalization". So a relativization of their proof would have to say: "if $TC0^{O} = PP^{O}$, then contradiction..." but this assumption is actually true for some oracles $O$.</p>

<p>In the comments, it was pointed out that $LOGSPACE^{O} = PSPACE^{O}$ in the way that I am using it. These are just subtleties with the oracle mechanism. On the LOGSPACE side, the query tape cannot be part of the space bound, since queries are polynomial length. On the PSPACE side, the query tape <em>is</em> taken as part of the space bound. That was to make things "fair". But if you give them exactly the same oracle mechanism then indeed you can separate them again by diagonalization. For instance, if queries do not count towards the space bound, then in PSPACE^{PSPACE} you can ask exponentially long questions to PSPACE, so this in fact contains EXPSPACE. I apologize for not saying this explicitly earlier. </p>

<p><strong>Space-bounded computation is very subtle with respect to oracles.</strong> See page 5 of <a href="http://www.cs.uchicago.edu/~fortnow/papers/relative.ps">this article by Fortnow</a> for a good summary of why oracle and space-bounded computation don't always mix.</p>

CC BY-SA 3.0
2018-02-28T19:31:26.950Z
See also [Aehlig, Cook and Nguyen, Relativizing small complexity classes and their theories](https://arxiv.org/abs/1204.5508).
Yuval Filmus
CC BY-SA 2.5
2010-09-19T00:05:30.447Z
Thanks for the comment about PSPACE^{PSPACE} containing EXPSPACE in the model that we used for LOGSPACE. My confusion has been cleared.
Robin Kothari
CC BY-SA 2.5
2010-09-18T17:33:30.450Z
2010-09-18T23:07:19.553Z
2010-09-18T23:07:19.553Z
Ryan Williams
<p>This is a follow up to this <a href="https://cstheory.stackexchange.com/questions/80/which-results-in-complexity-theory-make-essential-use-of-uniformity">question</a>, and is related to this <a href="https://cstheory.stackexchange.com/questions/1388/proofs-barriers-and-p-vs-np">question</a> of Shiva Kinali.</p>

<p>It seems that the proofs in these papers (<a href="http://ftp.cs.rutgers.edu/pub/allender/threshold.pdf" rel="nofollow noreferrer">Allender</a>, <a href="http://www.iro.umontreal.ca/~mckenzie/camcthvo97.ps" rel="nofollow noreferrer">Caussinus-McKenzie-Therien-Vollmer</a>, <a href="http://arxiv.org/abs/0902.1866" rel="nofollow noreferrer">Koiran-Perifel</a>) use hierarchy theorems. I want to know if the proofs are "<em>pure</em>" diagonalization theorems, or if they use something more that usual diagonalization. So my question is </p>

<blockquote>
  <p>is there a reasonable relativization which puts permanent in uniform $\mathsf{TC^0}$?</p>
</blockquote>

<p>Note that I am not sure how to define oracle access for uniform $\mathsf{TC^0}$, I know that finding the correct definition for small complexity classes is nontrivial. Another possibility is that permanent is not complete for $\mathsf{\#P}$ in the relativized universe, in which case I should use some complete problem for $\mathsf{\#P}$ in the relativized universe in place of it, and I think $\mathsf{\#P}$ should have a complete problem in any reasonable relativized universe.</p>

CC BY-SA 2.5
2010-09-17T20:43:17.833Z
How do you define a relativized version of the permanent?  Or are you looking for a relativized world where PP⊆TC^0?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-17T21:55:35.380Z
@Tsuyoshi: The problem is I am not sure about the proof that permanent being complete for $sharpP$. It seems to me that the proof that permanent is not in uniform $TC^0$ works also for any other complete problem. A reasonable relativization that puts $sharpP$ inside $TC^0$ would answer my question.
Kaveh
CC BY-SA 2.5
2010-09-18T06:02:36.797Z
I'm not sure what you mean by "reasonable" relativization. For any two complexity classes, one can make them equal by taking a strong enough oracle, no? E.g. $AC0^{PSPACE} = PSPACE = PSPACE^{PSPACE}$. (The first class is $AC0$ with "QBF gates".)
Ryan Williams
CC BY-SA 2.5
2010-09-18T07:49:12.820Z
@Ryan: I thought that the way one defines the oracle access is important, and if the definition is not right then strange things can happen. For example see this http://cs.toronto.edu/~sacook/homepage/rel-web.ps. (note: I didn't remember that they also discuss $TC^0$.) A machine with more resources can ask more complicated questions than a more restricted one form the same oracle and that is the reason that we don't have a (reasonable) relativization that would make DTime(n)=DTime($n^2$), so it seems to me that it is not as straight forward as you say, is it?
Kaveh
CC BY-SA 2.5
2010-09-18T07:51:17.487Z
$AC^0 = LH$ (log time hierarchy) $ \subset PH \subseteq PSpace$, so there should not be a reasonable relativization which would make $AC^0 = PSpace$. I feel that something is probably wrong with my reasoning in the previous line, do we know $LH \subset PH$?
Kaveh
CC BY-SA 2.5
2010-09-18T09:46:53.537Z
It's true that $TIME(n) \neq TIME(n^2)$ relativizes, but for two classes closed under "polynomial resources" (the kind under discussion), I think my comment holds. (Informally, by "polynomial resources" I mean it's possible to ask polynomial length queries to oracles.) To prove $AC0^{PSPACE} = PSPACE$, all you need is a PSPACE language that's complete under $AC0$ reductions. Take the Space-Bounded Halting Problem for an example. What I am curious about is what you mean by "reasonable". Is a PSPACE oracle unreasonable?
Ryan Williams
CC BY-SA 2.5
2010-09-18T15:53:04.873Z
@Ryan: I see. Yes, PSpace is a reasonable for me. I had two things in my mind when I used the word "reasonable". First, I wanted to avoid the possibility of having a definition of oracle access that would allow things like $NL(\alpha) \not \subset P(\alpha)$ for some $\alpha$. The second reason was to rule out a relativized world in which $SharpP$ does not have a complete problem.
Kaveh
CC BY-SA 2.5
2010-09-18T15:54:30.500Z
By the way, can I conclude from your comment that their proofs does not relativize? i.e. there is something more than a pure diagonalization in their proofs. (It would be nice if you combine your comments into an answer so I can accept it.)
Kaveh
CC BY-SA 2.5
2010-09-18T18:28:06.543Z
I'm a bit confused about the answers here and what the OP really meant to ask. Kaveh says, "can I conclude from your comment that their proofs does not relativize? i.e. there is something more than a pure diagonalization in their proofs." By which Kaveh means that diagonalization proofs always relativize. But in the model that we're working in, $L^{QBF}$ = $PSPACE^{QBF}$, but L and PSPACE can be separated by direct diagonalization.
Robin Kothari
CC BY-SA 2.5
2010-09-18T20:02:28.807Z
The answer to the question "is there a reasonable relativization which puts permanent in uniform TC0?" is yes. But I am also confused about how this relates to the rest. There is an implicit assumption that "pure diagonalization" means "relativizing" but as you can see things are more subtle than this, especially with respect to space-bounded classes. I was asked to put my observations as an answer, so I did...
Ryan Williams
CC BY-SA 2.5
2010-09-18T22:40:48.987Z
@Ryan: Thank you. @Robin: Sorry, but I think I am the person who is confusing things here. :) I did assume that "pure diagonaliztion"="relativizing diagonalization". But I am still confused, doesn't the space hierarchy theorem relativize? So there shouldn't be any oracles s.t. $L^O=PSpace^O$? But from what Ryan wrote, $L^TQBF=PSpace=PSpace^TQBF$!
Kaveh
<cc.complexity-theory><lower-bounds><relativization><permanent>
Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?
Kaveh
# Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

(Asked by: username_0 on 2010-09-17)

This is a follow up to this [question](https://cstheory.stackexchange.com/questions/80/which-results-in-complexity-theory-make-essential-use-of-uniformity), and is related to this [question](https://cstheory.stackexchange.com/questions/1388/proofs-barriers-and-p-vs-np) of Shiva Kinali.

It seems that the proofs in these papers ([Allender](http://ftp.cs.rutgers.edu/pub/allender/threshold.pdf), [Caussinus-McKenzie-Therien-Vollmer](http://www.iro.umontreal.ca/~mckenzie/camcthvo97.ps), [Koiran-Perifel](http://arxiv.org/abs/0902.1866)) use hierarchy theorems. I want to know if the proofs are "*pure*" diagonalization theorems, or if they use something more that usual diagonalization. So my question is

> is there a reasonable relativization which puts permanent in uniform $\mathsf{TC^0}$?

Note that I am not sure how to define oracle access for uniform $\mathsf{TC^0}$, I know that finding the correct definition for small complexity classes is nontrivial. Another possibility is that permanent is not complete for $\mathsf{\#P}$ in the relativized universe, in which case I should use some complete problem for $\mathsf{\#P}$ in the relativized universe in place of it, and I think $\mathsf{\#P}$ should have a complete problem in any reasonable relativized universe.

**Tags:** cc.complexity-theory, lower-bounds, relativization, permanent
> **Comments:**
> **username_1**: How do you define a relativized version of the permanent?  Or are you looking for a relativized world where PP⊆TC^0?  
> **username_0**: @Tsuyoshi: The problem is I am not sure about the proof that permanent being complete for $sharpP$. It seems to me that the proof that permanent is not in uniform $TC^0$ works also for any other complete problem. A reasonable relativization that puts $sharpP$ inside $TC^0$ would answer my question.  
> **username_2**: I'm not sure what you mean by "reasonable" relativization. For any two complexity classes, one can make them equal by taking a strong enough oracle, no? E.g. $AC0^{PSPACE} = PSPACE = PSPACE^{PSPACE}$. (The first class is $AC0$ with "QBF gates".)  
> **username_0**: @Ryan: I thought that the way one defines the oracle access is important, and if the definition is not right then strange things can happen. For example see this http://cs.toronto.edu/~sacook/homepage/rel-web.ps. (note: I didn't remember that they also discuss $TC^0$.) A machine with more resources can ask more complicated questions than a more restricted one form the same oracle and that is the reason that we don't have a (reasonable) relativization that would make DTime(n)=DTime($n^2$), so it seems to me that it is not as straight forward as you say, is it?  
> **username_0**: $AC^0 = LH$ (log time hierarchy) $ \subset PH \subseteq PSpace$, so there should not be a reasonable relativization which would make $AC^0 = PSpace$. I feel that something is probably wrong with my reasoning in the previous line, do we know $LH \subset PH$?  
> **username_2**: It's true that $TIME(n) \neq TIME(n^2)$ relativizes, but for two classes closed under "polynomial resources" (the kind under discussion), I think my comment holds. (Informally, by "polynomial resources" I mean it's possible to ask polynomial length queries to oracles.) To prove $AC0^{PSPACE} = PSPACE$, all you need is a PSPACE language that's complete under $AC0$ reductions. Take the Space-Bounded Halting Problem for an example. What I am curious about is what you mean by "reasonable". Is a PSPACE oracle unreasonable?  
> **username_0**: @Ryan: I see. Yes, PSpace is a reasonable for me. I had two things in my mind when I used the word "reasonable". First, I wanted to avoid the possibility of having a definition of oracle access that would allow things like $NL(\alpha) \not \subset P(\alpha)$ for some $\alpha$. The second reason was to rule out a relativized world in which $SharpP$ does not have a complete problem.  
> **username_0**: By the way, can I conclude from your comment that their proofs does not relativize? i.e. there is something more than a pure diagonalization in their proofs. (It would be nice if you combine your comments into an answer so I can accept it.)  
> **username_3**: I'm a bit confused about the answers here and what the OP really meant to ask. Kaveh says, "can I conclude from your comment that their proofs does not relativize? i.e. there is something more than a pure diagonalization in their proofs." By which Kaveh means that diagonalization proofs always relativize. But in the model that we're working in, $L^{QBF}$ = $PSPACE^{QBF}$, but L and PSPACE can be separated by direct diagonalization.  
> **username_2**: The answer to the question "is there a reasonable relativization which puts permanent in uniform TC0?" is yes. But I am also confused about how this relates to the rest. There is an implicit assumption that "pure diagonalization" means "relativizing" but as you can see things are more subtle than this, especially with respect to space-bounded classes. I was asked to put my observations as an answer, so I did...  
> **username_0**: @Ryan: Thank you. @Robin: Sorry, but I think I am the person who is confusing things here. :) I did assume that "pure diagonaliztion"="relativizing diagonalization". But I am still confused, doesn't the space hierarchy theorem relativize? So there shouldn't be any oracles s.t. $L^O=PSpace^O$? But from what Ryan wrote, $L^TQBF=PSpace=PSpace^TQBF$!  

---

## 1 answers

### Answer by username_2 on 2010-09-18. Score: 18 | Accepted answer

Any separation of classes closed under "polynomial resources" has an oracle making them equal. (This is provided the oracle mechanism is fair and allows both machine models to make polynomial length queries and no more.)

Let $TC0^{O}$ be "$TC0$ with gates for oracle $O$". Letting $O$ be a $PSPACE$-complete language under $TC0$ reductions, we have $TC0^{O} = PSPACE = PSPACE^{O} = PP^{O}$, where in the oracle mechanism for $PSPACE$, we count the space usage of the oracle tape along with the rest of the memory. (So only polynomially length queries are asked.) Such an equality holds for many classes "closed under polynomial resources", in the sense that they can ask polynomially length queries to an oracle, but no larger. These classes include stuff like $AC0$, $TC0$, $LOGSPACE$ (under a different oracle mechanism which does not count oracle queries towards the space bound), $P$, $NP$, $PH$, and $PP$. So any separation of classes in this list must necessarily use some kind of "non-relativizing" argument. This also implies (for example) that the natural proofs of things like Parity not in $AC0$ are non-relativizing (but this is even easier: all you need here is an oracle for parity, so you get $AC0[2]$).

In the collection of proofs you cite, I believe most of them (if not all) work by assuming $TC0 = PP$ and deriving a contradiction. These kinds of results are called "indirect diagonalization". So a relativization of their proof would have to say: "if $TC0^{O} = PP^{O}$, then contradiction..." but this assumption is actually true for some oracles $O$.

In the comments, it was pointed out that $LOGSPACE^{O} = PSPACE^{O}$ in the way that I am using it. These are just subtleties with the oracle mechanism. On the LOGSPACE side, the query tape cannot be part of the space bound, since queries are polynomial length. On the PSPACE side, the query tape *is* taken as part of the space bound. That was to make things "fair". But if you give them exactly the same oracle mechanism then indeed you can separate them again by diagonalization. For instance, if queries do not count towards the space bound, then in PSPACE^{PSPACE} you can ask exponentially long questions to PSPACE, so this in fact contains EXPSPACE. I apologize for not saying this explicitly earlier.

**Space-bounded computation is very subtle with respect to oracles.** See page 5 of [this article by Fortnow](http://www.cs.uchicago.edu/~fortnow/papers/relative.ps) for a good summary of why oracle and space-bounded computation don't always mix.

> **Comments:**
> **username_3**: Thanks for the comment about PSPACE^{PSPACE} containing EXPSPACE in the model that we used for LOGSPACE. My confusion has been cleared.  
> **username_4**: See also [Aehlig, Cook and Nguyen, Relativizing small complexity classes and their theories](https://arxiv.org/abs/1204.5508).  

---

