Hard promise problems and nonuniform complexity (Q1261468): Difference between revisions

The paper contains relativizations and generalizations of classical results of \textit{K.-I. Ko} [On self-reducibility and weak \(p\)-selectivity, J. Comput. System Sci. 26, 209-211 (1983; Zbl 0519.68062)]; \textit{K.-I. Ko} and \textit{U. Schöning} [On circuit-size and the low hierarchy in NP, SIAM J. Comput 14, 41-51 (1985; Zbl 0562.68033)]; and \textit{J. L. Balcázar}, \textit{R. V. Book}, \textit{U. Schöning} [ The polynomial hierarchy and sparse oracles, J. Assoc. Comput. Mach. 33, 603-617 (1986; Zbl 0625.68033)]. Some of the results might become more perspicuous if the hypothesis ``\(B\) is a solution of \(PP-A\)'' is replaced by ``\(A\) is \(p\)-selective relative to \(B\)''.