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?
-
2$\begingroup$ 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). $\endgroup$– Joshua GrochowDec 11, 2021 at 17:17
1 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:
If a class $\mathcal{C}$ is closed under exp-time Turing reductions, then $\mathsf{P}^{\mathcal{C}} = \mathsf{EXP}^{\mathcal{C}} = \mathcal{C}$.
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.)
-
$\begingroup$ Does this also apply to other strange collapses? For instance, $\mathsf{P}^\mathsf{ALL}$ = $\mathsf{ALL}^\mathsf{ALL}$ = $\mathsf{ALL}$. $\endgroup$– DemiDec 11, 2021 at 8:26
-
$\begingroup$ 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}}$. $\endgroup$ Dec 11, 2021 at 8:38
-
$\begingroup$ $\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? $\endgroup$– DemiDec 11, 2021 at 9:06
-
$\begingroup$ @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. $\endgroup$ Dec 11, 2021 at 9:49
-
2$\begingroup$ 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. $\endgroup$ Dec 11, 2021 at 14:44