Maurer, Peter M.2011-05-132011-05-132011-05-13http://hdl.handle.net/2104/8184The 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.71194 bytesapplication/pdfen-USSymmetric Boolean FunctionsNP-CompletenessConjugate SymmetryGeneralized Symmetry