文章基本信息
- 标题：Symmetric Logspace is Closed Under Complement
- 本地全文：下载
- 作者：Noam Nisan ; Amnon Ta-Shma
- 期刊名称：Chicago Journal of Theoretical Computer Science
- 印刷版ISSN：1073-0486
- 出版年度：1995
- 卷号：1995
- 出版社：MIT Press ; University of Chicago, Department of Computer Science
- 摘要：
We present a Logspace, many-one reduction from the undirected s-t connectivity problem to its complement. This shows that SL=coSL.
