On boolean lowness and boolean highness

DOI10.1016/S0304-3975(00)00146-8MaRDI QIDQ5941441zbMATH OpenFDO

Authors S. Reith, K. W. Wagner

Publication date 20 August 2001

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

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00146-8

zbMATH Keywords

adviceBoolean hierarchyBoolean highnessBoolean lownesscollapsecomputational complexityhardeasyhighnesslownesspolynomial-time hierarchy

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

The concepts of lowness and highness originate from recursion theory and were introduced into the complexity theory by \textit{U. Schöning} [Lect. Notes Comput. Sci. 211 (1985; Zbl 0589.03022)]. Informally, a set is low (high resp.) for a relativizable class \(K\) of languages if it does not add (adds maximal resp.) power to \(K\) when used as an oracle. In this paper, we introduce the notions of boolean lowness and boolean highness. Informally, a set is boolean low (boolean high resp.) for a class \(K\) of languages if it does not add (adds maximal resp.) power to \(K\) when combined with \(K\) by boolean operations. We prove properties of boolean lowness and boolean highness which show a lot of similarities with the notions of lowness and highness. Using Kadin's technique of hard strings [see \textit{J. Kadin}, SIAM J. Comput 17, No. 6, 1263-1282 (1988; Zbl 0664.03031); \textit{K. W. Wagner}, Number-of-query hierachies, TR 158, University of Augsburg (1987); \textit{R. Chang} and \textit{J. Kadin}, SIAM J. Comput. 25, No. 2, 340-354 (1996; Zbl 0844.68048); (*) \textit{R. Beigel, R. Chang} and \textit{M. Ogiwara}, Math. Syst. Theory 26, No. 3, 293-310 (1993; Zbl 0776.68043)] we show that the sets which are boolean low for the classes of the boolean hierarchy are low for the boolean closure of \(\Sigma_{2}^{p}\). Furthermore, we prove a result on boolean lowness which has as a corollary the best known result (*); in fact even a bit better) on the connection of the collapses of the boolean hierarchy and the polynomial-time hierarchy if \(BH = NP(k)\) then \(PH = \Sigma_{2}^{k-1}\oplus NP(k)\).

Recommendations

• scientific article; zbMATH DE number 1222828
• scientific article; zbMATH DE number 1008510
• The Boolean Hierarchy I: Structural Properties
• Generalized lowness and highness and probabilistic complexity classes
• scientific article; zbMATH DE number 3988706

Cites work

• A low and a high hierarchy within NP
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Automorphisms of the lattice of recursively enumerable sets
• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 3988706 (Why is no real title available?)
• Minimal pairs and high recursively enumerable degrees
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The Boolean Hierarchy I: Structural Properties
• The difference and truth-table hierarchies for NP
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

Cited in

(7)

• Boolean operations, joins, and the extended low hierarchy
• A note on parallel queries and the symmetric-difference hierarchy.
• scientific article; zbMATH DE number 1222828 (Why is no real title available?)
• Generalized lowness and highness and probabilistic complexity classes
• Lowness results: the next generation
• The Boolean hierarchy of NP-partitions
• Generalized modal satisfiability

This page was built for publication: On boolean lowness and boolean highness

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