The Complexity of Detecting Symmetric Functions

DSpace/Manakin Repository

BEARdocs is currently undergoing a scheduled upgrade. We expect the upgrade to be completed no later than Monday, March 2nd, 2015. During this time you will be able to access existing documents, but will not be able to log in or submit new documents.

Show simple item record Maurer, Peter M.
dc.description.abstract The characterization of the symmetries of boolean functions is important both in automatic layout synthesis, and in automatic verification of manually created layouts. It is possible to characterize the symmetries of an n-input boolean function as an arbitrary subgroup, G, of S(n), the symmetric group of order n. Given an expression e, which represents an n-input boolean function F, and a subgroup G of S(n) the problem of whether F possesses symmetry G is an NP-complete problem. The concept of an orbit can be used to characterize the various types of symmetry for a specified number of inputs. This classification can then be used, along with a few partitioning rules to completely determine the symmetries of a Boolean function. This technique requires that the truth-table of a function be completely enumerated, and thus has a running time proportional to 2^n where n is the number of inputs of the function. Some of the mathematical concepts presented to support the NP-completeness result have intriguing possibilities for circuit minimization. en
dc.subject Theoretical Computer Science en
dc.subject Algorithms en
dc.subject NP-Completeness en
dc.title The Complexity of Detecting Symmetric Functions en
dc.license GPL en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search BEARdocs

Advanced Search


My Account