Bounding the complexity of advice functions
Ricard Gavaldà · 2003
It is known that every set A in P/poly has an advice function in PF ( Sigma /sub 2//sup P/(A)). It is shown that A also has an advice function in PF(NP(A) (+) Sigma /sub 3//sup P/). From this bound, it is shown that separating Delta /sub 2//sup P/ and Sigma /sub 2//sup P/ relative to a set in P/poly is as hard as obtaining the same separation, unrelativized.>