TY - GEN

T1 - Complexity of circuit value and network stability

AU - Mayr, Ernst W.

AU - Subramanian, Ashok

PY - 1989

Y1 - 1989

N2 - A method for nontrivially restricting fanout in a circuit is developed. The complexity of the circuit value problem and a new problem, network stability, is studied when fanout is limited. This leads to new classes of problems within P. It is conjectured 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. 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 are obtained.

AB - A method for nontrivially restricting fanout in a circuit is developed. The complexity of the circuit value problem and a new problem, network stability, is studied when fanout is limited. This leads to new classes of problems within P. It is conjectured 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. 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 are obtained.

UR - http://www.scopus.com/inward/record.url?scp=0024898389&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0024898389

SN - 0818619589

T3 - Proc Struct Complexity Theor Fourth Ann Conf

SP - 114

EP - 123

BT - Proc Struct Complexity Theor Fourth Ann Conf

A2 - Anon, null

PB - Publ by IEEE

T2 - Proceedings: Structure in Complexity Theory - Fourth Annual Conference

Y2 - 19 June 1989 through 22 June 1989

ER -