Symmetric Logspace is Closed Under Complement

Authors

  • Noam Nisan
  • Amnon Ta-Shma

DOI:

https://doi.org/10.7146/brics.v1i31.21612

Abstract

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

Downloads

Published

1994-09-30

How to Cite

Nisan, N., & Ta-Shma, A. (1994). Symmetric Logspace is Closed Under Complement. BRICS Report Series, 1(31). https://doi.org/10.7146/brics.v1i31.21612

Issue

No. 31 (1994): RS-31 Symmetric Logspace is Closed Under Complement

Section

Articles

License

Creative Commons License

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.