文章基本信息

标题：Bounds on Monotone Switching Networks for Directed Connectivity
本地全文：下载
作者：Aaron Potechin
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：
We prove that any monotone switching network solving directed connectivity on N vertices must have size at least N(logN)
关键词：logarithmic space; non-deterministic logarithmic space; switching networks