REPORTS > DETAIL:
Paper:
TR94-003 | 12th December 1994 00:00
Symmetric Logspace is Closed Under Complement
TR94-003 Authors: Noam Nisan, Amnon Ta-Shma
Publication: 12th December 1994 00:00
Downloads: 114
Keywords:
Abstract:
We present a Logspace, many-one reduction from the undirected st-connectivity problem to its complement. This shows that $SL=co-SL$