Symmetry and complexity
László Babai, Robert Beals, Pál Takácsi-Nagy · 1992
We examine the effect of symmetry on the complexity of Boolean functions and find a remarkably tight hierarchy.Generalizing the fact that all symmetric Boolean functions belong to (nonuniform) Z'CO, we find that the complexity of the class of Boolean functions admitting a given group of symmetries is essentially determined by a single parameter of that group.