6
$\begingroup$

Edited at 2010/11/29:

As John Watrous have mentioned, the class $\mathsf{C^O}$ may be not well-defined. After reading some early posts, I try to restate my question in an unambiguous way.

Let $\mathsf{O}$ be a complexity class that is closed under complement, i.e. $\mathsf{O} = \mathsf{coO}$. Also we assume that the logspace, $\mathsf{L}$, is a subset of $\mathsf{O}$.

When does the equality $\mathsf{L^O} = \mathsf{O}$ hold?

We define $\mathsf{L^O}$ as languages accepted by logspace oracle machines with an $\mathsf{O}$ oracle, where queries are written on a separated oracle tape not restricted to the logspace bound, and after each query the tape is automatically erased.

We know that $\mathsf{NL} = \mathsf{coNL}$ by Immerman-Szelepcsényi Theorem, and we have $\mathsf{L^{NL}} = \mathsf{NL}$. Before the era of Reingold, when nobody knows whether $\mathsf{SL} = \mathsf{L}$, Nisan and Ta-Shma have proved that $\mathsf{SL}$ is closed under complement. They also show that $\mathsf{L^{SL}} = \mathsf{SL}$ in the paper.

In the paper "Directed Planar Reachability Is in Unambiguous Log-Space" by Bourke, Tewari and Vinodchandran, they gave a claim in corollary 4.3 that $\mathsf{L^{UL \cap coUL}} = \mathsf{UL \cap coUL}$. Clearly $\mathsf{UL \cap coUL}$ is closed under complement, but is this equality holds so trivially?

Do we have any easy conditions to decide if $\mathsf{L^O}$ and $\mathsf{O}$ are in fact the same? For easy conditions it means we only have to check some properties about $\mathsf{O}$, then we can decide if they are equal, without using definitions of the classes to prove the inclusion $\mathsf{L^O} \subseteq \mathsf{O}$.

Another related question would be:

Do we have any oracle $\mathsf{O}$ such that $\mathsf{L^O} \neq \mathsf{O}$?

Improve this question
$\endgroup$
7
  • $\begingroup$ Do you know anything about the extremal case where $C = O$? $\endgroup$
    – András Salamon
    Commented Nov 26, 2010 at 16:04
  • $\begingroup$ We do have $\mathsf{P^P} = \mathsf{P}$ and $\mathsf{EXP^{EXP}} \neq \mathsf{EXP}$; it seems that one needs to be able to simulate an $\mathsf{O}$-oracle call in $\mathsf{O}$ at least. But I do not know any conditions that can guarantee the equality holds i.e. $\mathsf{O^O} = \mathsf{O}$ when $\mathsf{C} = \mathsf{O}$. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Nov 26, 2010 at 16:46
  • $\begingroup$ For the second question, sure, e.g. take $O$ to be the empty set. $\endgroup$
    – Kaveh
    Commented Nov 28, 2010 at 17:16
  • 1
    $\begingroup$ If $O$ is not closed under log-space Turing reductions then this still holds and there are such $O$, so you may want to state that $O$ is closed under composition at least, in which case I think the question becomes "is log-space Turing reductions the same as log-space many-one reductions?" which is probably open. $\endgroup$
    – Kaveh
    Commented Nov 28, 2010 at 17:26
  • 1
    $\begingroup$ It is not open for all of them, it is well-known that the two reductions are not equivalent for some large classes. $\endgroup$
    – Kaveh
    Commented Nov 29, 2010 at 6:18

2 Answers 2

Reset to default
7
$\begingroup$

Edit: In revision 1, I wrote an embarrassingly complicated answer. The answer below is much simpler and stronger than the older answer.

Edit: Even the “simplified” answer in revision 2 was more complicated than necessary.

Let O be a complexity class that is closed under complement, i.e. O=coO. Also we assume that the logspace, L, is a subset of O.
[…]
Do we have any oracle O such that LO≠O?

Yes. Let O=RE∪coRE, where RE is the class of recursively enumerable languages. Then O is closed under complement and O contains L. However, note that LO=LRE, and in particular LO has a complete language under polynomial-time many-one reducibility. On the other hand, O=RE∪coRE does not have a complete language under polynomial-time reducibility because RE≠coRE. Therefore, LO≠O.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Is $\mathsf{L}$ a syntactic class? I mean, does $\mathsf{L^O}$ always have a complete language? If so, haven't your revisions 2 and 3 proved that for any complexity class $\mathsf{K}$ which is not closed under complement and contains $\mathsf{L}$, we have $\mathsf{L^{K \cup coK}} \neq \mathsf{K \cup coK}$? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Nov 29, 2010 at 6:59
  • $\begingroup$ @Hsien-Chih: If K has a complete language X (for example, if K=RE, we can let X=HALT), then L^{K∪coK}=L^K has the following canonical complete language: Given a Turing machine M, input x and a string 1^k, does M^X accepts x while using at most lg k work space? Note that we need a K-complete language to do this. (Here completeness means completeness under many-one reducibility.) $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 29, 2010 at 11:41
  • $\begingroup$ Yes you are right, I just wonder whether $\mathsf{L^O}$ has a complete language for every $\mathsf{O}$. In Thm 8.2 of haegar.informatik.uni-wuerzburg.de/TRs/tr372.ps, it claims that for a syntactic class say $\mathsf{P}$, $\mathsf{P^O}$ always have a complete language under polynomial many-one reductions. I am curious if this is true for logspace many-one reductions. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Nov 29, 2010 at 12:13
  • $\begingroup$ @Hsien-Chih: I am afraid that you are confusing a class with a language. In your question, O is a class. On the other hand, “every oracle X” in Theorem 8.2 in your link is a language. For example, P^AH (where AH is the arithmetic hierarchy) does not have a complete language (because P^AH=AH), but this does not contradict Theorem 8.2. $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 29, 2010 at 13:33
  • $\begingroup$ That is where my problems are!! Thank you! :) $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Nov 29, 2010 at 14:57
10
$\begingroup$

For a given choice of complexity classes $\mathsf{C}$ and $\mathsf{O}$, by which we mean sets of languages and nothing else, the class $\mathsf{C}^{\mathsf{O}}$ is not well-defined: we need the definition of $\mathsf{C}$ to determine how oracle queries are defined. Sometimes even then there could be ambiguities that need to be resolved, or the definition might not provide a reasonable notion of an oracle query at all. (Attaching oracles to space-bounded complexity classes is one example in the first category, where the relativized classes we obtain are very sensitive to the exact capabilities of the oracle tape and whether we consider that it contributes to our space bounds.)

So, I don't think you can possibly say anything about $\mathsf{C}^{\mathsf{O}}$ without using the definitions of the classes, because if you don't use the definition of $\mathsf{C}$ you aren't working with a well-defined mathematical object.

If I have misunderstood your question, please clarify what sort of properties of $\mathsf{C}$ and $\mathsf{O}$ you permit to be used.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You are correct; I did not aware that $\mathsf{C^O}$ may be not well-defined. I'll try to modify my question, please correct me if it is still problematic. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Nov 28, 2010 at 16:18
  • 2
    $\begingroup$ @Hsien-Chih Chang: Fenner, Fortnow, Kurtz and Li 2003 define a notion called “relativizable complexity class,” which is a mapping C which takes a language A to a complexity class C^A satisfying certain properties. This notion may be useful to make the original question (revision 1 or the question) rigorous without restricting the class C to a specific class. $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 29, 2010 at 1:24

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.