Chicago Journal of Theoretical Computer Science

Volume 1995

Article 1

Published by MIT Press. Copyright 1995 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe for legitimate access to all journal articles.

Symmetric Logspace is Closed Under Complement

Noam Nisan (Hebrew University), Amnon Ta-Shma (Hebrew University)
30 June, 1995

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

DOI: 10.4086/cjtcs.1995.001
[] Article 2
[back] Volume 1995 [back] Published articles
[CJCTS home]

Last modified: 24 March 1997