5 ms·
Undirected st-connectivity is UL complete (and by showing that it's in L it was shown that UL = L). Logarithmic space is just an arbitrary constraint. It could
by IsTom 15y ago
Undirected st-connectivity is UL complete (and by showing that it's in L it was shown that UL = L). Logarithmic space is just an arbitrary constraint. It could be polynomial or exp-space.