18 votes
Accepted

Potentially equal complexity classes without known contradictory relativizations

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, ...
16 votes
Accepted

Is ALogTime != PH hard to prove (and unknown)?

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 ...
13 votes

Is there a result in computability theory that does not relativize?

Higman's Embedding Theorem: The finitely generated computably presented groups are precisely the finitely generated subgroups of finitely presented groups. Furthermore, every computably presented ...
11 votes

More on PH in PP?

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 ...
9 votes
Accepted

What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

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 ...
8 votes
Accepted

Almost-P and related definitions

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 ...
7 votes
Accepted

What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

$\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 '...
7 votes

Oracle comparing $EXP$ with $UP$

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=...
7 votes
Accepted

Oracle comparing $EXP$ with $UP$

$\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}$ ...
6 votes
Accepted

Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

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 ...
6 votes

Is there a result in computability theory that does not relativize?

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 ...
5 votes

Potentially equal complexity classes without known contradictory relativizations

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

Relativized world in which P ≠ NP = coNP

Some oracles of this sort were given in other answers on this site: https://cstheory.stackexchange.com/a/1545 gives references to an oracle $A$ such that $\mathrm{EXP}^A=\mathrm{NP}^A=\mathrm{ZPP}^A$....
3 votes

Is there a result in computability theory that does not relativize?

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 ...
3 votes
Accepted

What is conjunctive truth table reduction?

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....
2 votes

Is ALogTime != PH hard to prove (and unknown)?

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 ...
2 votes

Is there a relativized form of Rice Theorem?

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 ...
2 votes
Accepted

Relativized world where $L^A=NP^A$

My question is just whether there is a known relativization barrier. Yes, there is a known relativization barrier. It's given by $A:=TQBF$, because Emil Jeřábek (see comments) is right: the statement ...

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