-2
$\begingroup$

How am I supposed to read the P=?NP relativization proof? I am reading

Theodore Baker, John Gill, and Robert Solovay. Relativization of the P=?NP problem. Siam Journal of Computing, 4:432-442, 1975 [219]

in particular the proof that there exist an oracle B such that P^B = NP^B on page 436. I have some questions and your help will be appreciated.

  • The procedure does not seem to be an oracle but a deterministic algorithm ... ?

  • Is this construction a counterexample to P = NP?

  • What does this mean "Run query machine P_i with oracle B_i on input x_i = 0^n?" Does it mean that P_i asks

a) if B_i accepts 0^n

b) if B_i accepts any string of lenght n

c) ONE BY ONE if B_i accepts a string of length n from the canonical enumeration?

  • I assume that the set B or B_i is initially empty. Does it mean that the FIRST string of length n form the canonical enumeration will always be added?

PSEUDOCODE:

http://xnewberry.tripod.com/Relativization.pdf

$\endgroup$

closed as off-topic by Emil Jeřábek, Gamow, Jan Johannsen, D.W., Sasho Nikolov Sep 9 at 18:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Gamow, Jan Johannsen, D.W., Sasho Nikolov
If this question can be reworded to fit the rules in the help center, please edit the question.