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