Hard promise problems and nonuniform complexity

From MaRDI portal





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\).











This page was built for publication: Hard promise problems and nonuniform complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1261468)