NL/poly ⊆ ⊕L/poly
Avi Wigderson · 2002
The article provides logspace analogs of the results of Valiant-Vazirani (L.G. Valiant and V.V. Vazirsni, 1986). We first show that solving STCONN for graphs with at most one st-path is essentially as hard as the general problem, via a probabilistic logspace reduction. We derive from it a nonuniform logspace reduction from NL to /spl oplus/L.>