Bounds on monotone switching networks for directed connectivity
arXiv:0911.0664
Abstract
We separate monotone analogues of L and NL by proving that any monotone switching network solving directed connectivity on vertices must have size at least .
49 pages, 12 figures