Better than Brute ForceEugene M. LuksUniversity of Oregon
October 19,

ABSTRACT


A classic problem in logic design involves testing whether two Boolean functions have the same network realization. This is the case if the functions are NPNequivalent, that is, related via permutations and negations of the m variables as well as negation of the function values. Proposed heuristics have been, in the worst case, no better than brute force enumeration of all the transformations. Even considering the input size to be n=2^m (functions are given via truth tables), the existence of a polynomialtime alternative was open. The question is equivalent to testing isomorphism of hypergraphs on m vertices in `simplyexponential' c^m time. Such betterthanbruteforce (m!) isomorphism had once appeared elusive even for ordinary graphs on m vertices. However, applying elementary group theory, we now handle the graph case using only naive divideandconquer. At first glance, there appear to be serious bottlenecks in an extension to hypergraphs. Nevertheless, a dynamicprogramming reorganization settles the hypergraph problem as well. In turn, this yields polynomial time for Booleanfunction equivalence. In fact, the procedure is strongly parallelizable. This is a joint meeting with the Theory of Computation Seminar. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

