ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR94-003 | 12th December 1994 00:00

Symmetric Logspace is Closed Under Complement

RSS-Feed




TR94-003
Authors: Noam Nisan, Amnon Ta-Shma
Publication: 12th December 1994 00:00
Downloads: 761
Keywords: 


Abstract:

We present a Logspace, many-one reduction from the undirected
st-connectivity problem to its complement. This shows that
$SL=co-SL$



ISSN 1433-8092 | Imprint