A low and a high hierarchy within NP
From MaRDI portal
Publication:1052097
DOI10.1016/0022-0000(83)90027-2zbMath0515.68046MaRDI QIDQ1052097
Publication date: 1983
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(83)90027-2
03F20: Complexity of proofs
Related Items
On the complexity of graph reconstruction, Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, Complete sets and closeness to complexity classes, Generalized lowness and highness and probabilistic complexity classes, A refinement of the low and high hierarchies, Upper bounds for the complexity of sparse and tally descriptions, UP and the low and high hierarchies: A relativized separation, On boolean lowness and boolean highness, Hyper-polynomial hierarchies and the polynomial jump, A note on P-selective sets and closeness, If not empty, NP-P is topologically large, Minimal pairs for P, Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes, Complexity results in graph reconstruction, The complexity of unions of disjoint sets, On some natural complete operators, On hardness of one-way functions, On helping by robust oracle machines, Does co-NP have short interactive proofs ?, Graph isomorphism is in the low hierarchy, Strong and robustly strong polynomial-time reducibilities to sparse sets, Turing machines with few accepting computations and low sets for PP, Logarithmic advice classes, Polynomial-time compression, On the power of enumerative counting, Hard promise problems and nonuniform complexity, A note on sparse sets and the polynomial-time hierarchy, Probabilistic complexity classes and lowness, Boolean operations, joins, and the extended low hierarchy, Space-efficient recognition of sparse self-reducible languages, The structure of the honest polynomial m-degrees, Locating \(P\)/poly optimally in the extended low hierarchy, Some connections between bounded query classes and non-uniform complexity., On the computational structure of the connected components of a hard problem, Reducing the number of solutions of NP functions, Competing provers yield improved Karp-Lipton collapse results, Sets with small generalized Kolmogorov complexity, Tally NP sets and easy census functions., New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., Nonuniform lowness and strong nonuniform lowness, A complexity theory for feasible closure properties, LWPP and WPP are not uniformly gap-definable, Graph Isomorphism is in SPP, Resource bounded immunity and simplicity, Separating the low and high hierarchies by oracles, Self-reducible sets of small density, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, Nonlevelable sets and immune sets in the accepting density hierarchy inNP
Cites Work
- Degrees of unsolvability: structure and theory
- A uniform approach to obtain diagonal sets in complexity classes
- A comparison of polynomial time reducibilities
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- A second step toward the polynomial hierarchy
- On the Structure of Polynomial Time Reducibility
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Inclusion complete tally languages and the Hartmanis-Berman conjecture
- Polynomial Time Enumeration Reducibility
- Recursively enumerable sets and degrees
- Computationally Related Problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
