principleMinor
Question about the Relativization barrier
Viewed 0 times
therelativizationbarrieraboutquestion
Problem
Baker, Gill, and Solovay has shown in their famous paper, that there are oracles $A$ and $B$ with $P^A = NP^A$ and $P^B \not= NP^B$. So, one can't solve the $P$ vs. $NP$ Problem
with methods like diagonalization alone.
To find the oracle $A$ is easy. But the construction of oracle $B$ is very
complicated in the paper. Can we use a simpler oracle?
Does anyone tried a $P$-complete oracle? Is $P^P \not= NP^P$?
Would this result be a solution of the $P$ vs. $NP$ Problem?
with methods like diagonalization alone.
To find the oracle $A$ is easy. But the construction of oracle $B$ is very
complicated in the paper. Can we use a simpler oracle?
Does anyone tried a $P$-complete oracle? Is $P^P \not= NP^P$?
Would this result be a solution of the $P$ vs. $NP$ Problem?
Solution
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.
Context
StackExchange Computer Science Q#156049, answer score: 7
Revisions (0)
No revisions yet.