CONSTRUCTING AN EXACT PARITY BASE IS IN RNC 2
Giulia Galbiati, Francesco Maffioli · Parallel Processing Letters · 1992
In this work we address the parallel complexity of two combinatorial problems, specifically the problems of the existence and of the construction of a parity base of preassigned weight (exact parity base for short) in a 0-1 weighted, represented matroid, subject to parity conditions. We prove that these problems lie in the parallel complexity class RNC 2, i.e. they are solvable with one-sided error by a logspace uniform family of bounded fan-in circuits of polynomial size and quadratic logarithmic depth which receive, in addition to the problem input, a polynomial number of random input bits. We also show that the more general cases of these problems, defined over matroids weighted with integral instead of 0-1 weights, also belong to RNC 2, as long as the weights are given in unary notation. As a consequence some special cases of these problems, which are of independent interest, belong to the same parallel complexity class: examples of these are the problem of the construction of a perfect matching of preassigned weight in a 0-1 weighted graph, recently addressed in [1], or that of the construction of a base of preassigned weight, in the intersection of two 0-1 weighted represented matroids.