go-v.orgcodex
Menu
Page tools

codex · Philosophy

Boolean hierarchy

The Boolean hierarchy is the hierarchy of Boolean combinations (intersection, union and complementation) of NP sets. Equivalently, the Boolean hierarchy can be described as the class of Boolean circuits over NP predicates. A collapse of the Boolean hierarchy would imply a collapse of the polynomial hierarchy.

Wikipedia contributors, "Boolean hierarchy", Wikipedia, revision 1368873464, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex