Bounding the Complexity of Advice Functions

摘要

It was known that every set A in P/poly has an advice function in PF(ΣP2(A)). This paper shows that A also has an advice function in PF(NP(A) ⊕ ΣP3). From this new bound, it is shown that separating ΔP2 and ΣP2 relative to a set in P/poly is as hard as obtaining the same separation, unrelativized.