Better than Brute Force

Eugene M. Luks

University of Oregon

October 19,
refreshments at 3:45pm


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 NPN-equivalent, 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 polynomial-time alternative was open.

The question is equivalent to testing isomorphism of hypergraphs on m vertices in `simply-exponential' c^m time. Such better-than-brute-force (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 divide-and-conquer. At first glance, there appear to be serious bottlenecks in an extension to hypergraphs. Nevertheless, a dynamic-programming reorganization settles the hypergraph problem as well. In turn, this yields polynomial time for Boolean-function equivalence. In fact, the procedure is strongly parallelizable.

This is a joint meeting with the Theory of Computation Seminar.

Speaker's Contact Info: luks(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on October 02, 2001 at 01:21 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.