Counting paths in planar width 2 branching programs
Meena Mahajan, Nitin Saurabh, Karteek Sreenivasaiah · 2012
We revisit the problem of counting paths in width-2 planar branching programs. We show that this is hard for Boolean NC 1 under ACC 0 [5] reductions, completing a proof strategy outlined in [3]. On the other hand, for several restricted instances of width-2 planar branching programs, we show that the counting problem is TC0-complete. We also show that nonplanar width-2 programs can be planarized in AC 0 [2]. Using the equivalence of planar width-2 programs with the reduced-form representation of positive rationals, we show that the evaluation problem for this representation in the Stern-Brocot tree is also NC 1 hard. In contrast, the evaluation problem in the continued fraction representation is in TC 0. 1