Computer Science Technical Reports
Permanent URI for this collectionhttps://hdl.handle.net/2104/4824
Browse
Browsing Computer Science Technical Reports by Subject "Algorithms"
Now showing 1 - 3 of 3
- Results Per Page
- Sort Options
Item The Complexity of Detecting Symmetric Functions(2009-02-18T17:23:29Z) Maurer, Peter M.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.Item A Quick Algorithm for Identifying Conjugate Groups in GF(2)(2009-02-18T17:19:42Z) Maurer, Peter M.This report gives the details an algorithm for determining whether two matrix groups are conjugate to one another. Each group is designated by a pair of matrices that generate the group. The algorithm is able to determine whether the two generated groups are conjugate to one another without actually generating the groups.Item A Search Strategy Using a Hamming-Distance Oracle(2009-08-04T16:47:04Z) Maurer, Peter M.The objective of the algorithm described in this report is to optimally guess a hidden binary string based on queries to an oracle where the length of the string is known beforehand. A C++ version of the algorithm is given along with a theoretical discussion of why the algorithm works. A discussion of the worst and average-case performance is given along with some discussion of optimality.