The complexity of circuit value and network stability

DOI10.1016/0022-0000(92)90024-DMaRDI QIDQ1190989zbMATH OpenOpenAlexFDO

Authors Ernst W. Mayr, Ashok Subramanian

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

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• The complexity of the comparator circuit value problem
• On the construction of parallel computers from various basis of Boolean functions
• Upper bounds for monotone planar circuit value and variants
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Parallel algorithms for the circuit value update problem

Cites work

• scientific article; zbMATH DE number 4027472 (Why is no real title available?)
• scientific article; zbMATH DE number 4047154 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 3558960 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A New Approach to Stable Matching Problems
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• A taxonomy of problems with fast parallel algorithms
• Classifying the computational complexity of problems
• College Admissions and the Stability of Marriage
• Fast parallel matrix and GCD computations
• Nondeterministic Space is Closed under Complementation
• On Relating Time and Space to Size and Depth
• On the construction of parallel computers from various basis of Boolean functions
• On uniform circuit complexity
• Problems complete for deterministic logarithmic space
• Space-bounded reducibility among combinatorial problems
• The method of forced enumeration for nondeterministic automata

Cited in

(11)

• On the construction of parallel computers from various basis of Boolean functions
• A sublinear parallel algorithm for stable matching
• scientific article; zbMATH DE number 1759463 (Why is no real title available?)
• Using maximal independent sets to solve problems in parallel
• Verifying minimum stable circuit values
• Adventures in monotone complexity and TFNP
• Algorithms and lower bounds for comparator circuits from shrinkage
• Fanout limitations on constraint systems
• The complexity of the comparator circuit value problem
• Parallel approximation algorithms for maximum weighted matching in general graphs
• Global similarity tests of physical designs of circuits: a complex network approach

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1190989)