I have some questions about Baker, Gill, Solovay proof of the existence of an oracle such that P^B != NP^B. The proof can be found in Siam Journal of Computing, 4:432-442, 1975 [219].
* Why Isn't this construction considered a counterexample to P = NP? And if it is not, can it be strengthened into one? It seems to me that we have constructed a language recognizable in NP time but not in P time.
* In the proof there is the sentence "If P_i^B(i) accepts 0^n, then place no string into B at this stage." How can this possibly happen?
I figured that, since B is intially empty, the oracle B(i) ALWAYS rejects. So the only reason why P_i would accept is some reason OTHER than a question to B(i). Please correct me if I am wrong.
The proof in question is verbatim reproduced below. The original paper is below.
http://xnewberry.tripod.com/Baker_Gill_Solovay_P_not_NP_relativized.pdf
https://pdfs.semanticscholar.org/7623/d361452a61e43cce6c36e3ac004ca799c95f.pdf
- Badges
- Science topic
- Similar topics
- Computer Science
- Computing