scientific article; zbMATH DE number 17529

zbMATH Open0756.68037MaRDI QIDQ3974853FDOQ3974853

Authors:

Publication date: 26 June 1992

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

complexity hierarchyrandom polynomial timeBoolean closure

Mathematics Subject Classification ID

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

Cited In (8)

• A downward translation in the polynomial hierarchy
• On computing Boolean connectives of characteristic functions
• Title not available (Why is that?)
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Intersection suffices for Boolean hierarchy equivalence
• On the power of deterministic reductions to C=P
• Preface
• A relationship between difference hierarchies and relativized polynomial hierarchies

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)