Bounds on monotone switching networks for directed connectivity
Aaron Potechin
所有作者
Aaron Potechin
文献摘要
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(Ω(lg(n))).