01.12.2008

It is shown that the problem of deciding and constructing a perfect matching in bipartite graphs G with the polynomial permanents of their n × n adjacency matrices A (perm(A) = n^O(1)) are in the deterministic classes NC² and NC³, respectively. We further design an NC³ algorithm for the problem of constructing all perfect matchings (enumeration problem) in a graph G with a permanent bounded by O(n^k). The basic step was the development of a new symmetric function method for the decision algorithm and the new parallel technique for the matching enumerator problem. The enumerator algorithm works in O(log³n) parallel time and O(n^3k+5.5 log n) processors. It entails among other things an efficient NC³-algorithm for computing small (polynomial bounded) arithmetic permanents and a sublinear parallel time algorithm for the bipartite matching with permanents up to 2^nc.
Concerning the circuit complexity of the logical permanent (cf. [Ra 85]), we display a class of bounded permanent problems, each of superpolynomial monotone circuit complexity n^{Ω(log n)}([Ra 85]), and which are computable within the uniform O(log² n) depth and O(n^4.5) size boolean circuits.