Skip to main content
Share Your Experience: Take the 2024 Developer Survey
11 votes
Accepted

Can two different complexity classes be equal relative to an oracle? Example request

Let $\mathsf{C}$ be a complexity class of your choice, let $\mathsf{O}$ be an oracle of your choice, and define $\mathsf{D} = \mathsf{C}^\mathsf{O}$. Then $\mathsf{C}^\mathsf{O} = \mathsf{D}^\mathsf{O}...
Yuval Filmus's user avatar
8 votes

Can two different complexity classes be equal relative to an oracle? Example request

See Ryan Williams' answer here. An easy example is that $\mathsf{AC^0}\neq \mathsf{AC^0[2]}$, but they are equal relative to a parity oracle.
Wei Zhan's user avatar
  • 1,183
7 votes
Accepted

Question about the Relativization barrier

If $B$ is chosen at random, then $\mathsf{P}^B \neq \mathsf{NP}^B$ almost surely. See for example lecture notes of Luca Trevisan, Schöning and Pruim's gem, or the original paper of Bennett and Gill.
Yuval Filmus's user avatar
4 votes

Do relativized relations between complexity classes tell us anything about the nonrelativized relation?

I am by no means an expert, but 2 things come to mind: Because if we know things like $A^L \neq B^L$, for some $L$, then a proof of $A = B$ need to be non-relativizing. This puts constrains on the ...
Bernardo Subercaseaux's user avatar
4 votes
Accepted

Does $A^B = A^C$ imply $B = C$?

Morally, yes, I agree. I believe what you write is correct and a reasonable way to think about things. You can stop reading here, but if you want to read longer musings/ramblings, continue on: ...
D.W.'s user avatar
  • 161k
3 votes

Can two equal classes be separated wrt an oracle?

While the other answer answers the question as posed (at least, given your definition of 'type of machine'), I still think the question is rather ill-posed and that resolving this is a solution as ...
Discrete lizard's user avatar
  • 8,248
3 votes
Accepted

Are all proof techniques which only look at black box behaviour of a TM relativizing?

A theorem about an oracle Turing machine $T^A$ (where $A$ is the oracle) is relativizing if it is of the form $$\forall A \,.\, \phi(T^A)$$ We say that the statement $\phi$ relativizes. There is no ...
Andrej Bauer's user avatar
  • 30.6k
3 votes
Accepted

Is the existence of an oracle such that $P^O = NP^O$ nontrivial?

The existence of an oracle with respect to which $\mathsf{P} = \mathsf{NP}$ shows that $\mathsf{P} \neq \mathsf{NP}$ cannot be proved using techniques that relativize such as diagonalization. In ...
Yuval Filmus's user avatar
3 votes
Accepted

Specific example of a problem that shows why **NP** isn't low for itself

As Pål GD mentions in the comments, $\mathsf{NP}^\mathsf{NP}$ is usually knows as $\mathsf{\Sigma}_2^P$, the second level of the polynomial hierarchy. If $L$ is any $\mathsf{\Sigma}_2^P$ complete ...
Yuval Filmus's user avatar
3 votes
Accepted

The power of relativised proofs

The reason has little to do with the problems in $\mathbf{P}$ and $\mathbf{NP}$ themselves; it is due to the computation models they describe. Recall that, if $A$ and $B$ are complexity classes, $A^B$ ...
dkaeae's user avatar
  • 5,027
3 votes

Why is $NP \subseteq P \implies NP^A \subseteq P^A$ false?

Your statement holds for all oracles $A$ iff $\mathsf{P} \neq \mathsf{NP}$. Indeed, if $\mathsf{P} \neq \mathsf{NP}$ then your statement vacuously holds. Conversely, if $\mathsf{P} = \mathsf{NP}$, ...
Yuval Filmus's user avatar
3 votes
Accepted

Show that $P^A \neq EXP^A$ for all oracles A

Why does the proof of the time hierarchy theorem relativize? The time hierarchy theorem is proved by diagonalization. Such proofs tend to relativize. In order to know for sure, all you have to do is ...
Yuval Filmus's user avatar
2 votes

How to tell if a proof relativizes?

A proof relativizes if every step in the proof relativizes. You should go over your proof, and check whether each step remains valid in the presence of an oracle. In contrast, a result relativizes by ...
Yuval Filmus's user avatar
2 votes

Finding a language that is $NP^L$-complete

What you are looking for is a relativization of the Cook-Levin theorem in the sense that you consider SAT and NP relative to an oracle for $L$. You can find the answer to that in this answer, point ...
dkaeae's user avatar
  • 5,027
2 votes

Confusion about $EXP \subseteq P^{EXPCOM}$ claim from Arora and Barak

You are correct that $T$ needs to know which Turing machine accepts $L$. This Turing machine is $M$, and you can hardcode it into $T$. There is absolutely no problem with that. Here is a similar ...
Yuval Filmus's user avatar
2 votes

A' not computable in A

You are right. It seems you completely understand this already: in any case the result can be found many places, as it is a basic result about the Turing degrees.
Bjørn Kjos-Hanssen's user avatar
1 vote
Accepted

Relativized world where $LogCFL^A=PSPACE^A$

Maybe it is easier to look at the problem from the other side: ... the German wikipedia article on NP claims that $LogCFL\neq PSPACE$ would be known, ... It is know: $CFL \subset DSPACE(O(\log^2 n))$ ...
Thomas Klimpel's user avatar

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