scientific article; zbMATH DE number 17529

MaRDI QIDQ3974853zbMATH OpenFDO

Authors

Publication date 26 June 1992

zbMATH Keywords

Boolean closurecomplexity hierarchyrandom polynomial time

Mathematics Subject Classification ID

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

Recommendations

• STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
• scientific article; zbMATH DE number 4033067
• The Boolean Hierarchy I: Structural Properties
• scientific article; zbMATH DE number 3988706
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

Cited in

(10)

• Nondeterministic and randomized Boolean hierarchies in communication complexity
• STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
• scientific article; zbMATH DE number 4033067 (Why is no real title available?)
• On the power of deterministic reductions to C=P
• On computing Boolean connectives of characteristic functions
• A downward translation in the polynomial hierarchy
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Preface
• Intersection suffices for Boolean hierarchy equivalence
• Nondeterministic and randomized Boolean hierarchies in communication complexity

This page was built for publication:

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