# Tag Info

24

As Steven notes, the canonical example is $\mathsf{IP} = \mathsf{PSPACE}$. This collapse does not relativize, in the sense that there is an oracle $A$, subject to which $\mathsf{IP}^A \ne \mathsf{PSPACE}^A$. The intuition why the known proof of this result avoids the relativization barrier is that it uses arithmetization (Yonatan alluded to this in a comment)...

18

I think the biggest such example at present is $BQP$ (quantum polybomial time) vs $PH$ (the polynomial time hierarchy). Significant effort has been put into separating them relative to an oracle, with no success. (Of course a powerful enough oracle will make them equal.) And the best known containment result is that $BQP$ is in $PP$. Some references ...

16

Not sure why Fortnow says there's "no meaningful model where $L$ and $NP$ collapse"... it seems to me that QBF should make them collapse, under the usual Ruzzo-Simon-Tompa oracle model (and the link you included agrees). Note this oracle model also has its quirks: we have $L = NL$ if and only if $L^A = NL^A$ for every oracle $A$, so any oracle witnessing a ...

14

You are exactly right. The relativization operation $B\mapsto B^A$ is not well defined. P and PA are independently defined objects. The names are suggestive, but you cannot formally define PA from the set P. (You can define P from PA by setting A to be the empty set.) Think of PA as being some kind of generalization of P, which equals P when A is empty, ...

14

I don't know a reference, but I think both of these should be doable. For your first oracle: for starters you'll want an oracle (call it $A_1$) that encodes exponentially-large $MAJORITY$ instances, and that thereby separates both $P^{A_1}$ and $NP^{A_1}$ from $PP^{A_1}$. Then you want a second oracle (call it $A_2$) that encodes the solutions to all $PH^{... 14 I had a vague recollection that I knew an excellent reference for such oracle separations. I finally found it. A great reference for oracle separations (for classes between P and PSPACE) is the following paper: Vereshchagin, N K (1994), "RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS", Russian Academy of Sciences. ... 12 Normally, the way people prove that a complexity theorem relativizes is using the following two-step procedure: Prove the theorem. Observe that your proof relativizes! In other words, that nothing in the proof changes at all if all the machines mentioned in the proof get access to the same oracle A. Yes, it's really as simple as that. To make it rigorous,... 12 For question 1, the BGS construction can be performed in exponential time, so you can construct such$B \in \mathsf{EXP}$. (For question 2: Sasho Nikolov's answer was originally only for$\mathsf{\Sigma_k P}$-complete languages, and I pointed out that one can also take any$B' \in \mathsf{NP} \cap \mathsf{coNP}$, since$\mathsf{NP}^{\mathsf{NP} \cap \mathsf{...

11

Higman's Embedding Theorem: The finitely generated computably presented groups are precisely the finitely generated subgroups of finitely presented groups. Furthermore, every computably presented group (even ones countably generated) is a subgroup of a finitely presented group. Note that this statement could relativize to: "The $O$-computably presented ...

11

For question 2, you can take any $B' \in \mathsf{PH}$ (this means you cannot bring down the $B$ in the BGS result down from $\mathsf{EXP}$ to $\mathsf{PH}$ without resolving the big question). Clearly for any $B'$, $P \subseteq \mathsf{P}^{B'} \subseteq \mathsf{NP}^{B'}$. Let $B' \in \Sigma_i^{\mathsf{P}}$. Recall that, by the definition of the Polynomial ...

11

From the comment above: there are two interpretations to your question: 1) The Cook-Levin theorem does not relativize in this sense: there exists a language $L$ and an oracle $A$ such that $L \in NP^A$ but $L$ is not polynomial-time many-one reducible to $3SAT$ even if the polynomial time Turing machine that performs the reduction is allowed to access the ...

9

The complexity zoo is your friend! As Robin said, you have half the answer: any EXP-complete problem collapses NP to P, and therefore BPP to P. Buhrman and Fortnow constructed an oracle relative to which P = RP but BPP is not equal to P. This is more than what you asked for; I suspect there are easier constructions that separate P from both RP and BPP.

9

By the work of Klivans and van Melkebeek (which relativizes), if E = DTIME($2^{O(n)}$) does not have circuits with PP gates of size $2^{o(n)}$ then PH is in PP. The contrapositive says that if PH is not in PP then E has subexponential-size circuits with PP gates. That is consistent with the fact that an oracle proof of PH not in PP gives a relativized lower ...

9

I believe if you trace through the argument given, e.g., in Section 4.1 of Ker-I Ko's survey, you get an upper bound of $\mathsf{DTIME}(2^{2^{O(n^2)}})$. In fact, we can replace $n^2$ here with any function $nf(n)$ where $f(n) \to \infty$ as $n \to \infty$. This isn't quite what was asked for, but it's close. In particular, using the translation between ...

8

The question seems to be predicated on a misunderstanding: the statements “relative to a random oracle $A$, $\mathrm{P}^A=\mathrm{BPP}^A$” and “$\mathrm{Almost\text-P}=\mathrm{BPP}$” are not meant to be rephrasings of each other. The complexity zoo refers to a paper of Bennett and Gill, which proves the former statement (and many other things) in detail, but ...

7

this is a nice survey of the field by a leading expert that summarizes/details some of the points of the other answers so far & has additional examples.  The Role of Relativization in Complexity Theory Fortnow Several recent nonrelativizing results in the area of interactive proofs have caused many people to review the importance of ...

7

A nice description of an oracle that separates P and BPP is given by Greg Kuperberg in one of the comments of this interesting blog post, where Terence Tao describes Turing machines with oracles and complexity results relative to oracles in the form of an allegory.

7

$\mathsf{MA_{EXP}} \not\subseteq \mathsf{P/poly}$ but there is an oracle relative to which this is false; both were proved in H. Buhrman, L. Fortnow, T. Thierauf. Nonrelativizing separations. CCC '98. (freely available author's version)

7

The quoted Beigel, Buhrman, and Fortnow paper gives a solution to 2 in Theorem 1.8: there is an oracle relative to which $\mathrm{P=Mod_3P}$ (which implies $\mathrm{P=UP}$), and $\mathrm{\oplus P=NP=EXP}$ (which, together with the first equality, actually implies $\mathrm{EXP=ZPP}$).

7

$\mathsf{UP} \neq \mathsf{EXP}$ is open. A UP-generic oracle* should make $\mathsf{P} \neq \mathsf{UP} = \mathsf{EXP}$, and since $\mathsf{UP} \subseteq \mathsf{\oplus P} \subseteq \mathsf{EXP}$ relative to any oracle, this should resolve 1. (I say "should" because I haven't checked all the details...) *UP-generic oracles are discussed, for example, by ...

6

On popular request, here is my comment as an answer: There is an oracle separating $\mathrm{PP}$ from $\mathrm{PSPACE}$: Jacobo Toran, A combinatorial technique for separating counting complexity classes, ICALP 1989. The best result for $\mathrm{P}^\mathrm{PP}$ that I know is a conditional result by Heribert Vollmer: Relating polynomial time to constant ...

5

I am not familiar with the notion of universal predictor, and I did not follow everything you wrote; in particular, I did not follow your sketch of the proof of existence of a universal predictor in E. But assuming that there exists a universal open predictor that belongs to E, the answer to your question is positive. And I am afraid that you will probably ...

5

(I assume this question will eventually get migrated to CS.SE, but I am posting my answer to it here on cstheory for now.) Technically, one doesn't usually think of relativization as an "operator" or "function"; however, I don't see a reason why you couldn't take a statement and map the statement to a relativized version of it. The trick is that, as others ...

5

Is there an oracle known to separate $\mathsf{P}^{\#\mathsf{P}}$ from $\mathsf{PSPACE}$?

4

The short version of this answer is: Degree theory (e.g. the study of the first-order theory of the partial order of Turing degrees) yields examples of non-relativizing statements, although these statements are of course highly technical. One useful tool for understanding this situation is the cone theorem ... which also limits the extent to which this ...

3

This is something I've often wondered about as well! If by "results in computability theory," you mean results that are invariant with respect to the choice of machine model (Turing machines, RAM machines, etc.), then I don't know a single example of such a result, and I definitely would've remembered if I'd seen one. The closest I can suggest to an answer ...

3

In the binary case they are two of the seven truth-table reducibilities $$m, btt(1), c, d, p, \ell, tt$$ based on polynomial clones. See Figure 1 in Culver's paper https://link.springer.com/article/10.1007/s00153-013-0351-x for the classic diagram of the seven. In the ternary case there are uncountably many such reducibilities instead of 7, as Culver ...

2

You can prove your idea via the usual recursion theorem proof of Rice's theorem. proof: Suppose that $M_{yes}$ is a machine with both property $P_1$ and $P_2$ and that $M_{no}$ is a machine with property $P_1$ but without property $P_2$. Such machines must exist by the nontrivial assumption. Then suppose there exists a decider $D$ which accepts any input ...

2

A naive idea for proving ALogTime != PH: The Boolean formula value problem is complete for ALogTime under deterministic log time reductions. Hence if ALogTime = PH, then PH = coNP = ALogTime, and hence the Boolean formula value problem would be complete under deterministic log time reductions for coNP. Hence there would be a deterministic log time reduction ...

Only top voted, non community-wiki answers of a minimum length are eligible