2
$\begingroup$

I'm trying to get a better handle on oracle separations between complexity classes but I keep running up against some (seemingly) silly issues that make me think that I'm fundamentally misunderstanding something (or more than one thing).

For example, I understand that for an oracle separation to hold in the unrelativized case it must hold for all possible oracles (which is why we cannot answer P=NP? this way). However, is it not true that for any two complexity classes we can always construct an oracle such that they are equivalent in relation to that oracle? For instance, by choosing a higher level of the arithmetic hierarchy to use as the oracle?

i.e. given two complexity classes $A$ and $B$ such that $A,B \subseteq \Sigma_{n}^{0}$, is it not always the case that $A^{\Sigma_{n+1}^{0}} = B^{\Sigma_{n+1}^{0}}$, given that the arithmetic hierarchy doesn't collapse? If not, why?

Improve this question
$\endgroup$
1
  • $\begingroup$ We prefer you ask only one question per question. I'll edit your question to remove the second question, but feel free to post it separately (you can find it by looking at the revision history -- click the "edited" link under the question). $\endgroup$
    – D.W. ♦
    Commented Jun 14, 2016 at 19:29

2 Answers 2

Reset to default
5
$\begingroup$

You seem to understand the concept even though you described it wrong. ​ ​ ​ Unless exactly one of {A,B} is uniform, an oracle separation of A from B either means ​ [showing that there is an oracle O such that ​ AO ≠ BO ] , ​ or means [exhibitings an oracle O such that ​ AO ≠ BO ].

Yes, it is "not true that for any two complexity classes we can always construct an oracle such that they are equivalent in relation to that oracle". ​ In particular, most hierarchy theorems relativize. ​ However, it is the case "that for any two complexity classes we can always construct" a class-oracle "such that they are equivalent in relation to that" class-oracle. ​ (For example, this one always does that.) ​ The triangle levels do not have complete sets with respect to syntactic subclasses of R, and each other non-computable level is not low for itself.

Given "two complexity classes $A$ and $B$ such that $A,B \subseteq \Sigma_{n}^{0}$," it is indeed "not always the case that $A^{\Sigma_{n+1}^{0}} = B^{\Sigma_{n+1}^{0}}$," even though "the arithmetic hierarchy doesn't collapse". ​ See two sentences before this sentence.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So in the specific case of the levels of the arithmetic hierarchy, because each individual level of the hierarchy does not contain complete problems with respect to the syntactic subclasses below it we cannot use them to create a class-oracle that would have the same properties as $A^{ALL}$ (to use the example you mentioned). Do I understand you correctly? $\endgroup$
    – nick.schachter
    Commented Jun 14, 2016 at 20:28
  • $\begingroup$ The $\Pi$ and $\Sigma$ levels do contain complete problems (even for fairly small reduction classes) which is why "we cannot use them to create a class-oracle that would" behave similarly to $A^{ALL}$. ​ ​ $\endgroup$
    – user12859
    Commented Jun 14, 2016 at 20:35
  • $\begingroup$ That is very confusing to me. If I have two complexity classes $A$ and $B$ that are contained in level $n$ of the arithmetic hierarchy, why wouldn't $A^{\Sigma _{n+1}^{0}} = B^{\Sigma _{n+1}^{0}}$? If each level of the hierarchy contains complete problems for a given reduction class, doesn't that imply that because $A,B \subseteq \Sigma _{n+1}^{0}$ we can reduce every problem in both $A$ and $B$ to an instance of a problem complete for $\Sigma _{n+1}^{0}$, which would then be solvable in $O(1)$ by the aforementioned oracle machines? $\endgroup$
    – nick.schachter
    Commented Jun 14, 2016 at 20:43
  • $\begingroup$ $\Sigma_{n+1}^0$ wouldn't be closed under complement. ​ The positive triangle levels presumably don't contain "complete problems for a given reduction class". ​ The other levels do, and "we can reduce every problem in both $A$ and $B$ to an instance of a problem complete for $\Sigma_{n+1}^0$, which would then be solvable in $O(1)$ by the aforementioned oracle machines", but on positive levels, we can't necessarily do that for other problems in $A^{\Sigma_{n+1}^0}$ and $B^{\Sigma_{n+1}^0}$. ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Jun 14, 2016 at 21:20
4
$\begingroup$

You are right, but I think you have a misunderstanding about what is meant by an oracle separation result. There are two common kinds of oracle separation results that I've seen in complexity theory. I'll illustrate them by talking about comparing the two complexity classes $P$ and $NP$, but the same applies to any other pair of complexity classes.

  1. A weaker result is to prove there exists an oracle $A$ such that $P^A=NP^A$ and there exists an oracle $B$ such that $P^B \ne NP^B$.

  2. A stronger result is to prove that, for a randomly chosen oracle $A$, we have $P^A \ne NP^A$ with high probability or for almost all $A$. (More precisely, the set $\{A : P^A \ne NP^A\}$ has measure 1.)

Both results imply that certain kinds of proof techniques are not going to work. In particular, relativizing proofs won't be strong enough to prove $P \ne NP$.

There are also other kinds of separation results. But none of these try to prove that $P^A \ne NP^A$ holds for all oracles $A$ (indeed, as you suggest, that isn't true).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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