Hard promise problems and nonuniform complexity

AbstractFor every recursive set A, let PP-A denote the following promise problem: input x and y promise (xϵA) ⊕ (yϵA) property xϵA.We show that if L is a solution of PP-A, then AϵPL/Poly. From this result, it follows that if A is ⩽PT-hard for NP, then all solutions of PP-A are hard for NP under a reduction that generalizes both ⩽PT and ⩽SNT. Specifically, if A is NP-hard, then all solutions of PP-A are generalized high2 (Balcázar et al., 1986). The main theorem that leads to this result states that if A is a self-reducible set and AϵPL/Poly, then ΣP,A2 ⊆ ΣP,L2. Several interesting connections between uniform and nonuniform complexity follow directly from this theorem