Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style
icon Submit Paper


RSS-Feed
REPORTS > DETAIL:

Paper:

TR94-003 | 12th December 1994 00:00

Symmetric Logspace is Closed Under Complement

Contact
Add Comment
RSS-Feed




TR94-003 Authors: Noam Nisan, Amnon Ta-Shma
Publication: 12th December 1994 00:00
Downloads: 3635
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