Boolean operations, joins, and the extended low hierarchy

DOI10.1016/S0304-3975(98)00006-1zbMath0913.68077MaRDI QIDQ1275091

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

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexity; closure properties; joins; extended low hierarchy; information extraction algorithms

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Structural properties of oracle classes, Tally NP sets and easy census functions., Hybrid Elections Broaden Complexity-Theoretic Resistance to Control

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• P-selectivity: Intersections and indices
• Turing machines that take advice
• 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
• Polynomial-Time Membership Comparable Sets
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy