<p>At first I thought this was just false, but then I saw some patterns that make it work. Here are two observations in converse directions:</p>
<ol>
<li><p>If a class <span class="math-container">$\mathcal{C}$</span> is closed under exp-time Turing reductions, then <span class="math-container">$\mathsf{P}^{\mathcal{C}} = \mathsf{EXP}^{\mathcal{C}} = \mathcal{C}$</span>.</p>
</li>
<li><p>If <span class="math-container">$\mathsf{P}^{\mathcal{C}} = \mathsf{EXP}^{\mathcal{C}}$</span>, then <span class="math-container">$\mathcal{C}$</span> does not contain a language that is complete under poly-time Turing reductions. For if <span class="math-container">$X$</span> were such a language, it would also be complete under exp-time Turing reductions, and then we'd have <span class="math-container">$\mathsf{P}^{\mathcal{C}} = \mathsf{P}^X \neq \mathsf{EXP}^X = \mathsf{EXP}^{\mathcal{C}}$</span>.</p>
</li>
</ol>
<p>(Interesting consequence A: because the Halting problem is <span class="math-container">$\mathsf{CE}$</span>-complete under poly-time Turing reductions, we have <span class="math-container">$\mathsf{P}^{\mathsf{CE}} = \mathsf{P}^{HALT} \neq \mathsf{EXP}^{HALT} = \mathsf{EXP}^{\mathsf{CE}}$</span>. Both these classes contain <span class="math-container">$\mathsf{CE} \cup \mathsf{coCE}$</span> and are contained in <span class="math-container">$\mathsf{\Delta}^0_2$</span>. I'd never thought about the fact that there is a relativized time hierarchy inside <span class="math-container">$\mathsf{\Delta}^0_2$</span> like this before. I think maybe at some point in my life I knew that the Halting problem was <span class="math-container">$\mathsf{\Delta}^0_2$</span> complete under Turing reductions but not under poly-time Turing reductions, but I had forgotten.)</p>
<p>(Slightly less interesting consequence <span class="math-container">$B$</span>: If a class is closed under exp-time Turing reductions, it does not have a complete language under poly-time Turing reductions.)</p>

CC BY-SA 4.0
2021-12-11T08:26:47.710Z
Does this also apply to other strange collapses?  For instance, $\mathsf{P}^\mathsf{ALL}$ = $\mathsf{ALL}^\mathsf{ALL}$ = $\mathsf{ALL}$.
Demi
CC BY-SA 4.0
2021-12-11T08:38:21.387Z
Well, $\mathsf{ALL}$ is kinda useless as a class of oracles, b/c in fact there is a single low-complexity machine $M$ (that just queries the oracle about the input) such that $\mathsf{ALL} = M^{\mathsf{ALL}}$. So any class of $\mathcal{M}$ oracle TMs that contains this machine $M$ has $\mathsf{ALL} = \mathcal{M}^{\mathsf{ALL}}$.
Joshua Grochow
CC BY-SA 4.0
2021-12-11T09:06:02.727Z
$\mathsf{ALL}$ is indeed useless, but classes like $\mathsf{PR}$ might not be.  Is there a way to generalize the statement that if a class satisfies sufficiently strong closure properties, it cannot have complete problems under somewhat weaker reductions?

To use an even more interesting example: my understanding is that there are problems that are $\mathsf{PSPACE}$-complete under $\mathsf{DTIME(O(n))}$ reductions, yet $\masthsf{P}^\mathsf{PSPACE} = \mathsf{PSPACE}$, seemingly contradicting the Time Hierarchy theorem.  What gives?
Demi
CC BY-SA 4.0
2021-12-11T09:49:16.093Z
@Demi: What is the linear-time complete problem for PSPACE? I'm not sure I know of one, and I'm pretty sure you just gave a proof that none exists.
Joshua Grochow
CC BY-SA 4.0
2021-12-11T14:44:25.420Z
There is no PSPACE-complete problem under linear-time reductions (or even linear-space reductions with linear output size). This would contradict the space hierarchy theorem.
Emil Jeřábek
CC BY-SA 4.0
2021-12-11T08:13:17.753Z
2021-12-11T08:13:17.753Z
Joshua Grochow
<p>Some classes, such as ALL, ELEMENTARY, and R, are very badly behaved when used as oracles.  For instance, all three of these classes trivially collapse P and EXP, even though (by the Time Hierarchy Theorem) those are distinct relative to any oracle.  What causes this behavior?</p>

CC BY-SA 4.0
2021-12-11T17:17:23.160Z
Why the votes to close? If you voted to close bc you think it belongs on CS.SE, take a look at my answer. Can you characterize the classes C for which P^C=EXP^C? That is essentially what the question seems to be asking, and that feels research-level to me (unless I'm missing some obvious answer).
Joshua Grochow
<cc.complexity-theory><computability>
Why are some classes (ALL, ELEMENTARY, R, etc) badly behaved as oracles?
Demi
# Why are some classes (ALL, ELEMENTARY, R, etc) badly behaved as oracles?

(Asked by: username_0 on 2021-12-11)

Some classes, such as ALL, ELEMENTARY, and R, are very badly behaved when used as oracles. For instance, all three of these classes trivially collapse P and EXP, even though (by the Time Hierarchy Theorem) those are distinct relative to any oracle. What causes this behavior?

**Tags:** cc.complexity-theory, computability

> **Comments:**
> **username_1**: Why the votes to close? If you voted to close bc you think it belongs on CS.SE, take a look at my answer. Can you characterize the classes C for which P^C=EXP^C? That is essentially what the question seems to be asking, and that feels research-level to me (unless I'm missing some obvious answer).  

---

## 1 answers

### Answer by username_1 on 2021-12-11. Score: 4 | Accepted answer

At first I thought this was just false, but then I saw some patterns that make it work. Here are two observations in converse directions:

1. If a class $\mathcal{C}$ is closed under exp-time Turing reductions, then $\mathsf{P}^{\mathcal{C}} = \mathsf{EXP}^{\mathcal{C}} = \mathcal{C}$.
2. If $\mathsf{P}^{\mathcal{C}} = \mathsf{EXP}^{\mathcal{C}}$, then $\mathcal{C}$ does not contain a language that is complete under poly-time Turing reductions. For if $X$ were such a language, it would also be complete under exp-time Turing reductions, and then we'd have $\mathsf{P}^{\mathcal{C}} = \mathsf{P}^X \neq \mathsf{EXP}^X = \mathsf{EXP}^{\mathcal{C}}$.

(Interesting consequence A: because the Halting problem is $\mathsf{CE}$-complete under poly-time Turing reductions, we have $\mathsf{P}^{\mathsf{CE}} = \mathsf{P}^{HALT} \neq \mathsf{EXP}^{HALT} = \mathsf{EXP}^{\mathsf{CE}}$. Both these classes contain $\mathsf{CE} \cup \mathsf{coCE}$ and are contained in $\mathsf{\Delta}^0\_2$. I'd never thought about the fact that there is a relativized time hierarchy inside $\mathsf{\Delta}^0\_2$ like this before. I think maybe at some point in my life I knew that the Halting problem was $\mathsf{\Delta}^0\_2$ complete under Turing reductions but not under poly-time Turing reductions, but I had forgotten.)

(Slightly less interesting consequence $B$: If a class is closed under exp-time Turing reductions, it does not have a complete language under poly-time Turing reductions.)

> **Comments:**
> **username_0**: Does this also apply to other strange collapses?  For instance, $\mathsf{P}^\mathsf{ALL}$ = $\mathsf{ALL}^\mathsf{ALL}$ = $\mathsf{ALL}$.  
> **username_1**: Well, $\mathsf{ALL}$ is kinda useless as a class of oracles, b/c in fact there is a single low-complexity machine $M$ (that just queries the oracle about the input) such that $\mathsf{ALL} = M^{\mathsf{ALL}}$. So any class of $\mathcal{M}$ oracle TMs that contains this machine $M$ has $\mathsf{ALL} = \mathcal{M}^{\mathsf{ALL}}$.  
> **username_0**: $\mathsf{ALL}$ is indeed useless, but classes like $\mathsf{PR}$ might not be.  Is there a way to generalize the statement that if a class satisfies sufficiently strong closure properties, it cannot have complete problems under somewhat weaker reductions?  To use an even more interesting example: my understanding is that there are problems that are $\mathsf{PSPACE}$-complete under $\mathsf{DTIME(O(n))}$ reductions, yet $\masthsf{P}^\mathsf{PSPACE} = \mathsf{PSPACE}$, seemingly contradicting the Time Hierarchy theorem.  What gives?  
> **username_1**: @username_0: What is the linear-time complete problem for PSPACE? I'm not sure I know of one, and I'm pretty sure you just gave a proof that none exists.  
> **username_2**: There is no PSPACE-complete problem under linear-time reductions (or even linear-space reductions with linear output size). This would contradict the space hierarchy theorem.  

---

