16
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ How do you define a relativized version of the permanent? Or are you looking for a relativized world where PP⊆TC^0? $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 17, 2010 at 20:43
  • $\begingroup$ @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. $\endgroup$
    – Kaveh
    Commented Sep 17, 2010 at 21:55
  • 2
    $\begingroup$ 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".) $\endgroup$
    – Ryan Williams
    Commented Sep 18, 2010 at 6:02
  • $\begingroup$ @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 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? $\endgroup$
    – Kaveh
    Commented Sep 18, 2010 at 7:49
  • $\begingroup$ $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$? $\endgroup$
    – Kaveh
    Commented Sep 18, 2010 at 7:51

1 Answer 1

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
2

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.