Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

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: 1440
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