Report Number: CS-TR-89-1278
Institution: Stanford University, Department of Computer Science
Title: The complexity of circuit value and network stability
Author: Mayr, Ernst W.
Author: Subramanian, Ashok
Date: August 1989
Abstract: We develop a method for non-trivially 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 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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/89/1278/CS-TR-89-1278.pdf