The complexity of circuit value and network stability

DOI10.1016/0022-0000(92)90024-DzbMath0762.68024OpenAlexW2173502887MaRDI QIDQ1190989

Ashok Subramanian, Ernst W. Mayr

Publication date: 27 September 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(92)90024-d

zbMATH Keywords

reducibilitycircuit value problemnetwork stability problem

Mathematics Subject Classification ID

Related Items (9)

Parallel approximation algorithms for maximum weighted matching in general graphs ⋮ Comparator circuits over finite bounded posets ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Using maximal independent sets to solve problems in parallel ⋮ Unnamed Item ⋮ Fanout limitations on constraint systems ⋮ Adventures in monotone complexity and TFNP ⋮ The complexity of the comparator circuit value problem ⋮ A sublinear parallel algorithm for stable matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the construction of parallel computers from various basis of Boolean functions
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• The method of forced enumeration for nondeterministic automata
• On uniform circuit complexity
• Space-bounded reducibility among combinatorial problems
• A taxonomy of problems with fast parallel algorithms
• Classifying the computational complexity of problems
• Problems complete for deterministic logarithmic space
• Nondeterministic Space is Closed under Complementation
• On Relating Time and Space to Size and Depth
• A New Approach to Stable Matching Problems
• Fast parallel matrix and GCD computations
• College Admissions and the Stability of Marriage

This page was built for publication: The complexity of circuit value and network stability