A low and a high hierarchy within NP
From MaRDI portal
Publication:1052097
DOI10.1016/0022-0000(83)90027-2zbMath0515.68046OpenAlexW2011042573MaRDI 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
Related Items (61)
New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. ⋮ The complexity of online bribery in sequential elections ⋮ A complexity theory for feasible closure properties ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ The structure of the honest polynomial m-degrees ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ Nonuniform lowness and strong nonuniform lowness ⋮ On hardness of one-way functions ⋮ On helping by robust oracle machines ⋮ Separating the low and high hierarchies by oracles ⋮ Does co-NP have short interactive proofs ? ⋮ Strong partial clones and the time complexity of SAT problems ⋮ Complexity results in graph reconstruction ⋮ Graph isomorphism is in the low hierarchy ⋮ On the complexity of graph reconstruction ⋮ Self-reducible sets of small density ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ A refinement of the low and high hierarchies ⋮ The extended low hierarchy is an infinite hierarchy ⋮ The join can lower complexity ⋮ Unnamed Item ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Link crossing number is NP-hard ⋮ The Complexity of Complexity ⋮ Unnamed Item ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Strong and robustly strong polynomial-time reducibilities to sparse sets ⋮ UP and the low and high hierarchies: A relativized separation ⋮ A note on P-selective sets and closeness ⋮ Turing machines with few accepting computations and low sets for PP ⋮ Logarithmic advice classes ⋮ The complexity of unions of disjoint sets ⋮ Polynomial-time compression ⋮ On the power of enumerative counting ⋮ If not empty, NP-P is topologically large ⋮ On boolean lowness and boolean highness ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Graph Isomorphism is in SPP ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Hardness of sparse sets and minimal circuit size problem ⋮ UP and the low and high hierarchies: A relativized separation ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ Hyper-polynomial hierarchies and the polynomial jump ⋮ Hard promise problems and nonuniform complexity ⋮ A note on sparse sets and the polynomial-time hierarchy ⋮ Probabilistic complexity classes and lowness ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ ⋮ Boolean operations, joins, and the extended low hierarchy ⋮ Sets with small generalized Kolmogorov complexity ⋮ Complete sets and closeness to complexity classes ⋮ Generalized lowness and highness and probabilistic complexity classes ⋮ Do there exist complete sets for promise classes? ⋮ Minimal pairs for P ⋮ Resource bounded immunity and simplicity ⋮ Tally NP sets and easy census functions. ⋮ On some natural complete operators ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes ⋮ On the computational structure of the connected components of a hard problem ⋮ Reducing the number of solutions of NP functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: A low and a high hierarchy within NP
