Why is Symmetry So Hard?

Publication Year:
2011
Usage 308
Abstract Views 229
Downloads 79
Repository URL:
http://hdl.handle.net/2104/8184
Author(s):
Maurer
Tags:
Symmetric Boolean Functions; NP-Completeness; Conjugate Symmetry; Generalized Symmetry
artifact description
The problem of detecting virtually any type of symmetry is shown to be co-NP-complete. We start with totally symmetric functions, then extend the result to partially symmetric functions, then to more general cofactor relations, and finally to generic permutation-group symmetries. We also show that the number of types of symmetry grows substantially with the number of inputs, compounding the complexity of an already difficult problem.