Boolean operations, joins, and the extended low hierarchy

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

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

Publication date: 12 January 1999

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00006-1

zbMATH Keywords

computational complexityclosure propertiesjoinsextended low hierarchyinformation extraction algorithms

Mathematics Subject Classification ID

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

Related Items (4)

Structural properties of oracle classes ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ Tally NP sets and easy census functions.

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

This page was built for publication: Boolean operations, joins, and the extended low hierarchy