I am trying to understand the relativization barrier from Baker Gill Solovay (BGS). About this barrier, I have heard that it only applies when using a black-box simulation. Hence, my question is, what would be an hypothetic white-box simulation (that would skip the relativization barrier)?

It seems to me that, the problem with a black-box simulation is that, if we build, for instance, a NP machine that simulates any P machine, then, we should be able to simulate any P machine with any oracle O, and BGS proved that there are some P machines and oracles O that cannot be simulated with an NP machine (with the same oracle O). Is this correct? If this is the case, I have the feeling that limiting the capabilities of the simulator might skip the relativization barrier, could it be?

For instance, if we limit the simulator to "only" simulate logspace reductions together with some (fixed) P machine solving a P-complete problem under logspace reductions (I think that this might not possible since a logspace reduction can output a polynomially large output, but lets assume that we could), then, the BGS counterexample would not apply since the counterexample is not written in the form expected by the simulator (the simulator expects a reduction). Would this be the case?

Any clarification or suggested sources to read about black-box vs white-box simulations would be appreciated.

  • $\begingroup$ The proof of IP=PSPACE is the canonical example of a non-relativizing proof. $\endgroup$ Commented Apr 11, 2022 at 18:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.