Hard promise problems and nonuniform complexity
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\).
- A comparison of polynomial time reducibilities
- A low and a high hierarchy within NP
- Arithmetical Reducibilities I
- Complexity Measures for Public-Key Cryptosystems
- Cryptocomplexity and NP-completeness
- scientific article; zbMATH DE number 3963808 (Why is no real title available?)
- NP is as easy as detecting unique solutions
- On Circuit-Size Complexity and the Low Hierarchy in NP
- On hiding information from an oracle
- On self-reducibility and weak P-selectivity
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP
- Promise problems complete for complexity classes
- Reductions on NP and p-selective sets
- Sparse Sets, Lowness and Highness
- Strong nondeterministic polynomial-time reducibilities
- The complexity of promise problems with applications to public-key cryptography
- The ellipsoid method and its consequences in combinatorial optimization
- The polynomial-time hierarchy and sparse oracles
- A hierarchy based on output multiplicity
- Space-efficient recognition of sparse self-reducible languages
- Unified Characterisations of Resolution Hardness Measures
- scientific article; zbMATH DE number 18529 (Why is no real title available?)
- Spectral bounds on general hard core predicates. (Extended abstract)
- scientific article; zbMATH DE number 1506074 (Why is no real title available?)
- scientific article; zbMATH DE number 874695 (Why is no real title available?)
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)