Complexity of Circuit Value and Network Stability

摘要

The authors develop a method for non-trivially restricting fanout in a circuit. They 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 with P. The authors 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 approximately limited, the authors get 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.