Bounds on Monotone Switching Networks for Directed Connectivity

DOI10.1145/3080520MaRDI QIDQ4640280zbMATHOpenAlexFDO

Authors Aaron Potechin

Publication date 17 May 2018

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

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)

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)))$.

Cited in

(4)

• Static-memory-hard functions, and modeling the cost of space vs. time
• 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

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)