DocumentCode
1992742
Title
NL/poly ⊆ ⊕L/poly
Author
Wigderson, Avi
Author_Institution
Hebrew Univ., Jerusalem, Israel
fYear
1994
fDate
28 Jun- 1 Jul 1994
Firstpage
59
Lastpage
62
Abstract
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 ⊕L
Keywords
computational complexity; graph theory; STCONN; Valiant-Vazirani; graphs; logspace analogs; nonuniform logspace reduction; probabilistic logspace reduction; st-path; universal hash function; Analog computers; Arithmetic; Boolean functions; Circuits; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location
Amsterdam
Print_ISBN
0-8186-5670-0
Type
conf
DOI
10.1109/SCT.1994.315817
Filename
315817
Link To Document