Why is Symmetry So Hard?
dc.contributor.author | Maurer, Peter M. | |
dc.date.accessioned | 2011-05-13T15:28:18Z | |
dc.date.available | 2011-05-13T15:28:18Z | |
dc.date.issued | 2011-05-13T15:28:18Z | |
dc.description.abstract | 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. | en |
dc.format.extent | 71194 bytes | |
dc.format.mimetype | application/pdf | |
dc.identifier.uri | http://hdl.handle.net/2104/8184 | |
dc.language.iso | en_US | |
dc.license | GPL | en |
dc.subject | Symmetric Boolean Functions | en |
dc.subject | NP-Completeness | en |
dc.subject | Conjugate Symmetry | en |
dc.subject | Generalized Symmetry | en |
dc.title | Why is Symmetry So Hard? | en |