Why is Symmetry So Hard
Peter Michael Maurer · 2011
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 permutationgroup 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.