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.

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

DOI: 10.4086/cjtcs.1995.001

---

Article 2
Volume 1995 Published articles

Last modified: 24 March 1997