2024/08/22 by Apers, Simon, Edenhofer, Roman
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2408.12473
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(log2 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 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.