The Complexity of Detecting Symmetric Functions

Simple item page
dc.contributor.authorMaurer, Peter M.
dc.date.accessioned2009-02-18T17:23:29Z
dc.date.available2009-02-18T17:23:29Z
dc.date.issued2009-02-18T17:23:29Z
dc.description.abstractThe 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.format.extent124850 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/2104/5267
dc.language.isoen_US
dc.licenseGPLen
dc.subjectTheoretical Computer Scienceen
dc.subjectAlgorithmsen
dc.subjectNP-Completenessen
dc.titleThe Complexity of Detecting Symmetric Functionsen

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
The Complexity of Detecting Symmetric Functions.pdf
Size:
121.92 KB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.96 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Computer Science Technical Reports