Skip to main content
simplified even further
Source Link
Tsuyoshi Ito
  • 16.6k
  • 2
  • 56
  • 106

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.

First assume NP≠coNP Let O=REcoRE, and let O=NP∪coNPwhere RE is the class of recursively enumerable languages. Then O is closed under complement and O contains L. However, note that LO=LNPRE, and in particular LO has a complete problem Xlanguage under polynomial-time many-one reducibility. If LO is equal to O=NP∪coNP, then X belongs to either NP or coNP, and in either case, NP=coNP, contradicting our assumption.

Next we remove the assumption NP≠coNP. Note that On the above argument relativizes. Thereforeother hand, take anyO=RE∪coRE does not have a complete language A such that NPA≠coNPAunder polynomial-time reducibility because RE≠coRE. Therefore, and O=NPA∪coNPA gives an unconditional example such that LO≠O.

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

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.

First assume NP≠coNP, and let O=NP∪coNP. Then O is closed under complement and O contains L. However, note that LO=LNP, and in particular LO has a complete problem X under polynomial-time many-one reducibility. If LO is equal to O=NP∪coNP, then X belongs to either NP or coNP, and in either case, NP=coNP, contradicting our assumption.

Next we remove the assumption NP≠coNP. Note that the above argument relativizes. Therefore, take any language A such that NPA≠coNPA, and O=NPA∪coNPA gives an unconditional example such that LO≠O.

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=REcoRE, 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.

simplified and strengthened the result
Source Link
Tsuyoshi Ito
  • 16.6k
  • 2
  • 56
  • 106

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

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?

I guess that there is a simpler and/or stronger answer, but anyway: yes, unless the polynomial hierarchy collapses to the second level (Σ2P=Π2P). Assuming Σ2P≠Π2P, we have LO≠O for O=PΣ2P[1] (that is, the class of problems solvable in polynomial time by using the Σ2P oracle only once)Yes.

IndeedFirst assume NP≠coNP, O contains L and let O=NP∪coNP. Then O is closed under complement. Lemma 3.3 of Buhrman and Fortnow [BF99] showsO contains L. However, note that Σ2P △ NP := {(XY)∪(YX):LO=LNP, and in particular LO has a complete problem X∈Σ2P under polynomial-time many-one reducibility. If LO is equal to O=NP∪coNP, then YX∈NP} is not contained in O unless Σ2P=Π2P. Note that Σ2P △ belongs to either NP is containedor coNP, and in LOeither case, NP=coNP, contradicting our assumption.

[BF99] Harry Buhrman and Lance FortnowNext we remove the assumption NP≠coNP. Two queries Note that the above argument relativizes. Journal of Computer and System Sciences Therefore, 59(2):182–194take any language A such that NPA≠coNPA, Oct. 1999and O=NPA∪coNPA gives an unconditional example such that LO≠O. http://dx.doi.org/10.1006/jcss.1999.1647

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?

I guess that there is a simpler and/or stronger answer, but anyway: yes, unless the polynomial hierarchy collapses to the second level (Σ2P=Π2P). Assuming Σ2P≠Π2P, we have LO≠O for O=PΣ2P[1] (that is, the class of problems solvable in polynomial time by using the Σ2P oracle only once).

Indeed, O contains L and O is closed under complement. Lemma 3.3 of Buhrman and Fortnow [BF99] shows that Σ2P △ NP := {(XY)∪(YX): X∈Σ2P, Y∈NP} is not contained in O unless Σ2P=Π2P. Note that Σ2P △ NP is contained in LO.

[BF99] Harry Buhrman and Lance Fortnow. Two queries. Journal of Computer and System Sciences, 59(2):182–194, Oct. 1999. http://dx.doi.org/10.1006/jcss.1999.1647

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

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.

First assume NP≠coNP, and let O=NP∪coNP. Then O is closed under complement and O contains L. However, note that LO=LNP, and in particular LO has a complete problem X under polynomial-time many-one reducibility. If LO is equal to O=NP∪coNP, then X belongs to either NP or coNP, and in either case, NP=coNP, contradicting our assumption.

Next we remove the assumption NP≠coNP. Note that the above argument relativizes. Therefore, take any language A such that NPA≠coNPA, and O=NPA∪coNPA gives an unconditional example such that LO≠O.

Source Link
Tsuyoshi Ito
  • 16.6k
  • 2
  • 56
  • 106

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?

I guess that there is a simpler and/or stronger answer, but anyway: yes, unless the polynomial hierarchy collapses to the second level (Σ2P=Π2P). Assuming Σ2P≠Π2P, we have LO≠O for O=PΣ2P[1] (that is, the class of problems solvable in polynomial time by using the Σ2P oracle only once).

Indeed, O contains L and O is closed under complement. Lemma 3.3 of Buhrman and Fortnow [BF99] shows that Σ2P △ NP := {(XY)∪(YX): X∈Σ2P, Y∈NP} is not contained in O unless Σ2P=Π2P. Note that Σ2P △ NP is contained in LO.

[BF99] Harry Buhrman and Lance Fortnow. Two queries. Journal of Computer and System Sciences, 59(2):182–194, Oct. 1999. http://dx.doi.org/10.1006/jcss.1999.1647