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

<p><em>Edit: Even the “simplified” answer in revision 2 was more complicated than necessary.</em></p>

<blockquote>
  <p>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.<br>
  […]<br>
  Do we have any oracle O such that L<sup>O</sup>≠O?</p>
</blockquote>

<p>Yes.  Let O=<a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aR#re" rel="nofollow">RE</a>∪<a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#core" rel="nofollow">coRE</a>, where RE is the class of recursively enumerable languages.  Then O is closed under complement and O contains L.  However, note that L<sup>O</sup>=L<sup>RE</sup>, and in particular L<sup>O</sup> 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, L<sup>O</sup>≠O.</p>

CC BY-SA 2.5
2010-11-29T06:59:48.977Z
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}$?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-29T11:41:50.823Z
@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.)
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-29T12:13:36.610Z
Yes you are right, I just wonder whether $\mathsf{L^O}$ has a complete language for every $\mathsf{O}$. In Thm 8.2 of http://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.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-29T13:33:12.610Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-29T14:57:49.853Z
That is where my problems are!! Thank you! :)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-28T20:04:16.177Z
2010-11-29T05:13:20.260Z
2010-11-29T05:13:20.260Z
Tsuyoshi Ito
<p>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.)</p>

<p>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.  </p>

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

CC BY-SA 2.5
2010-11-28T16:18:16.160Z
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.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-29T01:24:19.853Z
@Hsien-Chih Chang: [Fenner, Fortnow, Kurtz and Li 2003](http://dx.doi.org/10.1016/S0890-5401%2803%2900018-X) 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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-28T02:12:32.683Z
2010-11-28T02:12:32.683Z
John Watrous
<h2>Edited at 2010/11/29:</h2>

<p>As <a href="https://cstheory.stackexchange.com/questions/3330/dominations-under-oracles-which-is-closed-under-complement/3370#3370">John Watrous</a> have mentioned, the class $\mathsf{C^O}$ may be not well-defined. After <a href="https://cstheory.stackexchange.com/questions/2484/are-oracles-associative">reading</a> <a href="https://cstheory.stackexchange.com/questions/7/space-bounded-tms-and-oracles">some</a> <a href="https://cstheory.stackexchange.com/questions/268/is-there-a-definitive-reference-for-turing-machines-with-multiple-oracle-tapes">early</a> <a href="https://cstheory.stackexchange.com/questions/2490/is-p-pp-p-p">posts</a>, I try to restate my question in an unambiguous way.</p>

<p>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}$.</p>

<blockquote>
  <p>When does the equality $\mathsf{L^O} = \mathsf{O}$ hold?</p>
</blockquote>

<p>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.</p>

<p>We know that $\mathsf{NL} = \mathsf{coNL}$ by Immerman-Szelepcsényi Theorem, and we have $\mathsf{L^{NL}} = \mathsf{NL}$.
Before the era of <a href="http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps" rel="nofollow noreferrer">Reingold</a>, when nobody knows whether $\mathsf{SL} = \mathsf{L}$, Nisan and Ta-Shma have <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9065&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">proved</a> that $\mathsf{SL}$ is closed under complement. They also show that $\mathsf{L^{SL}} = \mathsf{SL}$ in the paper.</p>

<p>In the paper "<a href="http://cse.unl.edu/~rtewari/ccc07.pdf" rel="nofollow noreferrer">Directed Planar Reachability Is in Unambiguous Log-Space</a>" 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?</p>

<p>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}$. </p>

<p>Another related question would be:</p>

<blockquote>
  <p>Do we have any oracle $\mathsf{O}$ such that $\mathsf{L^O} \neq \mathsf{O}$?</p>
</blockquote>

CC BY-SA 2.5
2010-11-26T16:04:12.477Z
Do you know anything about the extremal case where $C = O$?
András Salamon
CC BY-SA 2.5
2010-11-26T16:46:03.240Z
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}$.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-28T17:16:08.627Z
For the second question, sure, e.g. take $O$ to be the empty set.
Kaveh
CC BY-SA 2.5
2010-11-28T17:19:14.447Z
We need that $\mathsf{L} \subseteq \mathsf{O}$, as stated in line 4. Sorry for the unclarity...
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-28T17:26:39.857Z
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.
Kaveh
CC BY-SA 2.5
2010-11-28T17:35:19.693Z
Is it open for every class $\mathsf{O}$, or known to be the same for some specific classes? If the latter is true, I would like to know any criterion to $\mathsf{O}$ to make these two notions equal.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-29T06:18:03.863Z
It is not open for all of them, it is well-known that the two reductions are not equivalent for some large classes.
Kaveh
<cc.complexity-theory><complexity-classes><oracles>
Dominations under oracles which is closed under complement?
Hsien-Chih Chang 張顯之
# Dominations under oracles which is closed under complement?

(Asked by: username_0 on 2010-11-26)

## Edited at 2010/11/29:

As [John Watrous](https://cstheory.stackexchange.com/questions/3330/dominations-under-oracles-which-is-closed-under-complement/3370#3370) have mentioned, the class $\mathsf{C^O}$ may be not well-defined. After [reading](https://cstheory.stackexchange.com/questions/2484/are-oracles-associative) [some](https://cstheory.stackexchange.com/questions/7/space-bounded-tms-and-oracles) [early](https://cstheory.stackexchange.com/questions/268/is-there-a-definitive-reference-for-turing-machines-with-multiple-oracle-tapes) [posts](https://cstheory.stackexchange.com/questions/2490/is-p-pp-p-p), 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](http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps), when nobody knows whether $\mathsf{SL} = \mathsf{L}$, Nisan and Ta-Shma have [proved](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9065&rep=rep1&type=pdf) 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](http://cse.unl.edu/~rtewari/ccc07.pdf)" 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}$?

**Tags:** cc.complexity-theory, complexity-classes, oracles
> **Comments:**
> **username_1**: Do you know anything about the extremal case where $C = O$?  
> **username_0**: 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}$.  
> **username_2**: For the second question, sure, e.g. take $O$ to be the empty set.  
> **username_0**: We need that $\mathsf{L} \subseteq \mathsf{O}$, as stated in line 4. Sorry for the unclarity...  
> **username_2**: 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.  
> **username_0**: Is it open for every class $\mathsf{O}$, or known to be the same for some specific classes? If the latter is true, I would like to know any criterion to $\mathsf{O}$ to make these two notions equal.  
> **username_2**: It is not open for all of them, it is well-known that the two reductions are not equivalent for some large classes.  

---

## 2 answers

### Answer by username_3 on 2010-11-28. Score: 7 | Accepted answer

*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](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aR#re)∪[coRE](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#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.

> **Comments:**
> **username_0**: 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}$?  
> **username_3**: @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.)  
> **username_0**: Yes you are right, I just wonder whether $\mathsf{L^O}$ has a complete language for every $\mathsf{O}$. In Thm 8.2 of http://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.  
> **username_3**: @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.  
> **username_0**: That is where my problems are!! Thank you! :)  

---

### Answer by username_4 on 2010-11-28. Score: 10

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: @Hsien-Chih Chang: [Fenner, Fortnow, Kurtz and Li 2003](http://dx.doi.org/10.1016/S0890-5401%2803%2900018-X) 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.  

---

