Computer Science

Colloquium Details

Better than Brute Force

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 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 has been 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.