Symmetric Logspace is Closed Under Complement

Noam Nisan
Amnon Ta-Shma

September 1994

Abstract:

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

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.