16

This is a follow up to this question, and is related to this question of Shiva Kinali.

It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) 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.

Community
  • 1
Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • 1
    How do you define a relativized version of the permanent? Or are you looking for a relativized world where PP⊆TC^0? – Tsuyoshi Ito Sep 17 '10 at 20:43
  • @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 Sep 17 '10 at 21:55
  • 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".) – Ryan Williams Sep 18 '10 at 06:02
  • @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 Sep 18 '10 at 07:49
  • $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 Sep 18 '10 at 07:51
  • 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 Sep 18 '10 at 09:46
  • @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 Sep 18 '10 at 15:53
  • 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 Sep 18 '10 at 15:54
  • 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 Sep 18 '10 at 18:28
  • 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 Sep 18 '10 at 20:02
  • @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 Sep 18 '10 at 22:40

1 Answers1

18

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 for a good summary of why oracle and space-bounded computation don't always mix.

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164