5
$\begingroup$

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?

$\endgroup$
1
  • 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$ Dec 11, 2021 at 17:17

1 Answer 1

4
$\begingroup$

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.)

$\endgroup$
5
  • $\begingroup$ Does this also apply to other strange collapses? For instance, $\mathsf{P}^\mathsf{ALL}$ = $\mathsf{ALL}^\mathsf{ALL}$ = $\mathsf{ALL}$. $\endgroup$
    – Demi
    Dec 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$
    – Demi
    Dec 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.