Bounds on Monotone Switching Networks for Directed Connectivity

DOI10.1145/3080520zbMATH Open1426.68104arXiv0911.0664OpenAlexW2963815293MaRDI QIDQ4640280FDOQ4640280

Authors: Aaron Potechin 

Publication date: 17 May 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We separate monotone analogues of L and NL by proving that any monotone switching network solving directed connectivity on $n$ vertices must have size at least $n^{(}Omega(lg(n)))$.

Full work available at URL: https://arxiv.org/abs/0911.0664

zbMATH Keywords

circuit lower boundsswitching networksNLLdirected connectivitymonotone computation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)

Cited In (4)

• The parameterized space complexity of model-checking bounded variable first-order logic
• Adventures in monotone complexity and TFNP
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• Static-memory-hard functions, and modeling the cost of space vs. time

This page was built for publication: Bounds on Monotone Switching Networks for Directed Connectivity

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