The join can lower complexity
From MaRDI portal
Publication:6184670
DOI10.1007/3-540-61332-3_159zbMath1529.68117OpenAlexW2098655063MaRDI QIDQ6184670
Osamu Watanabe, Zhigen Jiang, Jörg Rothe, Hemaspaandra, Lane A.
Publication date: 29 January 2024
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-61332-3_159
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- A low and a high hierarchy within NP
- Graph isomorphism is in the low hierarchy
- The polynomial-time hierarchy
- Probabilistic complexity classes and lowness
- Locating \(P\)/poly optimally in the extended low hierarchy
- Separating the low and high hierarchies by oracles
- On Circuit-Size Complexity and the Low Hierarchy in NP
- Sparse Sets, Lowness and Highness
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- The Extended Low Hierarchy is an Infinite Hierarchy
- Lower bounds for the low hierarchy
This page was built for publication: The join can lower complexity