The complexity of circuit value and network stability

摘要

We develop a method for nontrivially restricting fanout in a circuit. We study the complexity of the circuit value problem and a new problem, network stability, when fanout is limited. This leads to new classes of problems within P. We conjecture 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. When fanout is appropriately limited, we obtain positive results: 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.