BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-89-1278
       ENTRY:: January 05, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: The complexity of circuit value and network stability
        TYPE:: Technical Report
      AUTHOR:: Mayr, Ernst W.
      AUTHOR:: Subramanian, Ashok
        DATE:: August 1989
       PAGES:: 21
    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.
       NOTES:: [Adminitrivia V1/RAM/19950105]
         END:: STAN//CS-TR-89-1278