Abstract
We present a BQSPACE(O(log n))-procedure to count st-paths on directed graphs for which we are promised that there are at most polynomially many paths starting in s and polynomially many paths ending in t. For comparison, the best known classical upper bound in this case just to decide st-connectivity is DSPACE(O(log² n/ log log n)). The result establishes a new relationship between~BQL and unambiguity and fewness subclasses of NL. Further, we also show how to \emph{recognize} directed graphs with at most polynomially many paths between any two nodes in BQSPACE(O(log n)). This yields the first natural candidate for a language separating BQL from L and~BPL. Until now, all candidates potentially separating these classes were inherently promise problems.