HiveBrain v1.2.0
Get Started
← Back to all entries
principleMinor

Question about the Relativization barrier

Submitted by: @import:stackexchange-cs··
0
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?

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.