The join can lower complexity

DOI10.1007/3-540-61332-3_159MaRDI QIDQ6184670zbMATH OpenOpenAlexFDO

Authors Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Boolean operations, joins, and the extended low hierarchy
• Another note on the join property
• Lower bounds for the low hierarchy
• Joining non-low C.E. sets with diagonally non-computable functions
• scientific article; zbMATH DE number 1222828

Cites work

• A low and a high hierarchy within NP
• Graph isomorphism is in the low hierarchy
• scientific article; zbMATH DE number 1555921 (Why is no real title available?)
• Locating P/poly optimally in the extended low hierarchy
• Lower bounds for the low hierarchy
• On Circuit-Size Complexity and the Low Hierarchy in NP
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Probabilistic complexity classes and lowness
• Separating the low and high hierarchies by oracles
• Sparse Sets, Lowness and Highness
• The Extended Low Hierarchy is an Infinite Hierarchy
• The polynomial-time hierarchy

This page was built for publication: The join can lower complexity

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