CJTCS Volume 1995 Article 1

Symmetric Logspace is Closed Under Complement

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

Abstract

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

• Preformatted versions of the article
  • DVI (50,240 bytes)
  • PostScript (197,570 bytes)
  • PDF (205,325 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX ( cj95-01.tex , 27,989 bytes)
  • BIBTeX ( cj95-01.bib , 4,404 bytes)
  • Parameter settings for custom formatting ( cjropts.tex , 116 bytes)
  • Self citation in BIBTeX (305 bytes)
• Online discussion
• Instructions for Readers

---

Article 2
Volume 1995 Published articles

Last modified: 24 March 1997