Complexity of circuit value and network stability

Ernst W. Mayr; Ashok Subramanian

Complexity of circuit value and network stability

Ernst W. Mayr, Ashok Subramanian

Johann Wolfgang Goethe University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

14 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Proc Struct Complexity Theor Fourth Ann Conf
Editors	Anon
Publisher	Publ by IEEE
Pages	114-123
Number of pages	10
ISBN (Print)	0818619589
State	Published - 1989
Externally published	Yes
Event	Proceedings: Structure in Complexity Theory - Fourth Annual Conference - Eugene, OR, USA Duration: 19 Jun 1989 → 22 Jun 1989

Publication series

Name	Proc Struct Complexity Theor Fourth Ann Conf

Conference

Conference	Proceedings: Structure in Complexity Theory - Fourth Annual Conference
City	Eugene, OR, USA
Period	19/06/89 → 22/06/89

Cite this

@inproceedings{570d05e4d47c4b63a71ffe40e95bdac3,

title = "Complexity of circuit value and network stability",

abstract = "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.",

author = "Mayr, {Ernst W.} and Ashok Subramanian",

year = "1989",

language = "English",

isbn = "0818619589",

series = "Proc Struct Complexity Theor Fourth Ann Conf",

publisher = "Publ by IEEE",

pages = "114--123",

editor = "Anon",

booktitle = "Proc Struct Complexity Theor Fourth Ann Conf",

note = "Proceedings: Structure in Complexity Theory - Fourth Annual Conference ; Conference date: 19-06-1989 Through 22-06-1989",

}

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 -

Complexity of circuit value and network stability

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this