We show that hypergraph isomorphism can be tested in time O(c~n),where n is the size of the vertex set.In general,input of a hypergraph could require #OMEGA#(2~n) space,in which case the isomorphism test is in polynomial time.As a consequence,we put into polynomical time the classic problem of testing whether two Boolean functions,given by truth tables,are related via permutations and complementations of teh variables,and therefore have structurally identical network realizations.In fact,the method is parallelizable and we put the problem even into NC.We obtain similarly an NC test of equivalence of truth tables unber permutation of variables alone.
展开▼
