Skip to main content
2 of 4
C^O ill-defined, replace C with L

Dominations under oracles which is closed under complement?

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.

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}$?