The complexity of circuit value and network stability
Erik M. Mayr, A. Subramanian · 2003
A method for nontrivially restricting fanout in a circuit is developed. The complexity of the circuit value problem and a new problem, network stability, is studied when fanout is limited. This leads to new classes or problems within P. It is conjectured that the new classes are different from P and incomparable to NC. One of these classes, CC, contains several natural complete problems, including circuit value for comparator circuits, lex-first maximal matching, and problems related to stable marriage and stable roommates. A parallel algorithm for circuit value that runs in time about the square root of the number of gates, a linear-time sequential algorithm for network stability, and logspace reductions between circuit value and network stability are obtained.>