BRICS RS-94-31 Nisan & Ta-Shma: Symmetric Logspace is Closed Under Complement

BRICS

Basic Research in Computer Science

Symmetric Logspace is Closed Under Complement

Noam Nisan Amnon Ta-Shma

BRICS Report Series RS-94-31 ISSN 0909-0878 September 1994 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1994, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@daimi.aau.dk

Symmetric Logspace is Closed Under Complement ^{∗}

Noam Nisan noam@cs.huji.ac.il Amnon Ta-Shma am@cs.huji.ac.il

September 28, 1994

Abstract

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

1 Introduction

This paper deals with the complexity class symmetric Logspace, SL, defined by Lewis and Papadimitriou in [LP82]. This class can be defined in several equivalent ways:

1. Languages which can be recognised by symmetric nondeterministic Turing Machines that run within logarithmic space. See [LP82].

2. Languages that can be accepted by a uniform family of polynomial size contact schemes (also sometimes called switching networks.) See [Raz91].

3. Languages which can be reduced in Logspace via a many-one reduction to UST CON, the undirected st-connectivity problem.

A major reason for the interest in this class is that it captures the complexity of UST CON. The input to UST CON is an undirected graph G and two vertices in it s, t, and the input should be accepted if s and t are connected via a path in G. The similar problem, ST CON, where the graph G is allowed to be directed is complete for NL, non-deterministic Logspace. Several combinatorial problems are known to be in SL or co − SL, e.g. 2-colourability is complete in co − SL [Rei82].

The following facts are known regarding SL relative to other complexity classes in “the vicinity”:

L ⊆ SL ⊆ RL ⊆ NL.

Here, L is the class deterministic Logspace and RL is the class of problems that can be accepted with one-sided error by a randomized Logspace machine running in polynomial time. The containment SL ⊆ RL is the only non-trivial one in the line above and follows directly from the randomized Logspace algorithm for UST CON of [AKL^{+}79]. It is also known that SL ⊆ SC [Nis92], SL ⊆ ⨁ L [KW93] and SL ⊆ DSP ACE(log^{1.5} n) [NSW92].

∗This work was supported by BSF grant 92-00043 and by a Wolfeson award administered by the Israeli Academy of Sciences. The work was revised while visiting BRICS, Basic Research in Computer Science, Centre of the Danish National Research Foundation.

After the surprising proofs that NL is closed under complement were found [Imm88, Sze88], Borodin et al [BCD^{+}89] asked whether the same is true for SL. They could prove only the weaker statement, namely that SL ⊆ co − RL, and left “SL = co − SL?” as an open problem. In this paper we solve the problem in the affirmative by exhibiting a Logspace, many-one reduction from UST CON to its complement. Quite surprisingly the proof of our theorem does not use inductive counting, as do the proofs of NL = co − NL, and is in fact even simpler than them, however it uses the [AKS83] sorting networks.

Theorem 1 SL = co − SL.

It should be noted that the monotone analogues (see [GS91]) of SL and co − SL are known to be different [KW88].

As a direct corollary of our theorem, we get that L^{SL} = SL^{SL} = SL where L^{SL} is the class of languages accepted by Logspace oracle Turing machines with oracle from SL, and SL^{SL} is defined similarly, being careful with the way we allow queries (see [RST82]).

Corollary 1.1 L^{SL} = SL^{SL} = SL

This also shows that the “symmetric Logspace hierarchy” defined in [Rei82] collapses to SL.

2 Proof of Theorem

2.1 Overview of proof.

We show that we can upper and lower bound the number of connected components of a graph, using connectivity problems. We upper bound this number using a “transitive-closure” method, which can be easily done since we are allowed to freely use connectivity problems. However, trying to lower-bound the number of connected components this way requires negation. The heart of the proof lies in lower-bounding the number of connected components, and we achieve this in a surprisingly easy way, by computing a spanning forest.

In subsection 2.2 we show how to combine many connectivity problems to one single connectivity problem. In subsection 2.3 we show how to find a spanning forest using connectivity problems. In subsection 2.4 we show how to use this spanning forest to find the number of connected components of a graph, and how we solve the st non-connectivity problem with it.

2.2 Projections to UST CON.

In this paper we will use only the simplest kind of reductions, i.e. LogSpace uniform projection reductions [SV85]. Moreover, we will be interested only in reductions to UST CON. In this subsection we define this kind of reduction and we show some of its basic properties.

Notation 2.1 Given f : {0, 1}^{∗} ↦ {0, 1}^{∗} denote by f_{n} : {0, 1}^{n} ↦ {0, 1}^{∗} the restriction of f to inputs of length n. Denote by f_{n,k} the k’th bit function of f_{n}, i.e. if f_{n} : {0, 1}^{n} ↦ {0, 1}^{k(n)} then f_{n} = (f_{n,1}, …, f_{n,k(n)}).

Notation 2.2 We represent an n–node undirected graph G using \binom{n}{2} variables x⃗ = \{x_{i,j}\}_{1≤i<j≤n} s.t. x_{i,j} is 1 iff (i, j) ∈ E(G). If f(x⃗) operates on graphs , we will write f(G) meaning that the input to f is a binary vector of length \binom{n}{2} representing G.

Definition 2.1 We say that f : {0, 1}^{∗} ↦ {0, 1}^{∗} reduces to UST CON(m) , m = m(n), if there is a uniform family of Space(log(n)) functions {σ_{n,k}} s.t. for all n and k:

• σ_{n,k} is a projection, i.e.: σ_{n,k} is a mapping from {i, j}_{1≤i<j≤m} to {0, 1, x_{i}, ¬x_{i}}_{1≤i≤n}

• Given x⃗ define Gx⃗ to be the graph Gx⃗ = ({1, …, m}, E) where E = {(i, j) | σ_{n,k}(i, j) = 1 or σ_{n,k}(i, j) = x_{i} and x_{i} = 1 or σ_{n,k}(i, j) = ¬x_{i} and x_{i} = 0}. It should hold that f_{n,k}(x⃗) = 1 ⟺ there is a path from 1 to m in Gx⃗.

If σ is restricted to the set {0, 1, x_{i}}_{1≤i≤n} we say that f monotonically reduces to UST CON(m).

Lemma 2.1 If f has uniform monotone formulae of size s(n) then f is monotonically reducible to UST CON(O(s(n))).

Proof: Given a formula ϕ recursively build (G, s, t) as follows:

• If ϕ = x_{i} then build a graph with two vertices s and t, and one edge between them labelled with x_{i}.

• If ϕ = ϕ_{1} ∧ ϕ_{2}, and (G_{i}, s_{i}, t_{i}) the graphs for ϕ_{i}, i = 1, 2, then identify s_{2} with t_{1} and define s = s_{1}, t = t_{2}.

• If ϕ = ϕ_{1} ∨ ϕ_{2}, and (G_{i}, s_{i}, t_{i}) the graphs for ϕ_{i}, i = 1, 2, then identify s_{1} with t_{1} and s_{2} with t_{2} and define s = s_{1} = t_{1} and t = s_{2} = t_{2}.

Using the AKS sorting networks [AKS83], which belong to NC^{1} , we get:

Corollary 2.2 Sort : {0, 1}^{∗} ↦ {0, 1}^{∗} (which given a binary vector sorts it) is monotonically reducible to UST CON(poly).

Lemma 2.3 If f monotonically reduces to UST CON(m_{1}) and g reduces to UST CON(m_{2}) then f ∘ g reduces to UST CON(m_{1}^{2} · m_{2}) , where ∘ is the standard function composition operator.

Proof: f monotonically reduces to a graph with m_{1} vertices, where each edge is labelled with one of {0, 1, x_{i}}. In the composition function f ∘ g each x_{i} is replaced by x_{i} = g_{i}(y⃗) which can be reduced to a connectivity problem of size m_{2}. Replace each edge labelled x_{i} with its corresponding connectivity problem.

2.3 Finding a spanning forest.

In this section we show how to build a spanning forest using UST CON. This construction was also noticed by Reif and independently by Cook [Rei82].

Given a graph G index the edges from 1 to m. We can view the indices as weights to the edges, and as no two edges have the same weight, we know that there is a unique minimal spanning forest F. In our case, where the edges are indexed, this minimal forest is the lexicographically first spanning forest.

It is well known that the greedy algorithm finds a minimal spanning forest. Let us recall how the greedy algorithm works in our case. The algorithm builds a spanning forest F which is at the beginning empty F = ∨. Then the algorithm checks the edges one by one according to their order, for each edge e if e does not close a cycle in F then e is added to the forest, i.e. F = F ∪ {e}.

At first glance the algorithm looks sequential, however, claim 2.3 shows that the greedy algorithm is actually highly parallel. Moreover, all we need to check that an edge does not participate in the forest, is one st connectivity problem over a simple to get graph.

Definition 2.2 For an undirected graph G denote by LF F (G) the lexicographically first spanning forest of G. Let

SF (G) ↦ \{0, 1\}^{\binom{n}{2}} be:

SF_{i,j}(G) = \{ \begin{matrix}0 & (i, j) ∈ LF F (G) \\ 1 & otherwise \end{matrix}

Lemma 2.4 SF reduces to UST CON(poly)

Proof: Let F be the lexicographically first spanning forest of G. For e ∈ E define G_{e} to be the subgraph of G containing only the edges {e′ ∈ E | index(e′) < index(e)}.

Claim: e = (i, j) ∈ F ⟺ e ∈ E ∧ i is not connected to j in G_{e}.

Proof: Let e = (i, j) ∈ E. Denote by F_{e} the forest which the greedy algorithm built at the time it was checking e. So e ∈ F ⟺ e does not close a cycle in F_{e}.

(⟹) e ∈ F and therefore e does not close a cycle in F_{e}, but then e does not close a cycle in the transitive closure of F_{e}, and in particular e does not close a cycle in G_{e}.

(⟸) e does not close a cycle in G_{e} therefore e does not close a cycle in F_{e} and e ∈ F.

Therefore SF_{i,j}(G) = ¬x_{i,j} ∨ i is connected to j in G_{(i,j)}.

Since ¬x_{i,j} can be viewed as the connectivity problem over the graph with two vertices and one edge labelled ¬x_{i,j} it follows from lemmas 2.1, 2.3 that SF reduces to UST CON. Notice, however, that the reduction is not monotone.

2.4 Putting it together.

First, we want to build a function that takes one representative from each connected component. We define LI_{i}(G) to be 0 iff the vertex i has the largest index in its connected component.

Definition 2.3 LI(G) ↦ {0, 1}^{n}

LI_{i}(G) = \{ \begin{matrix}0 & i has the largest index in its connected component \\ 1 & otherwise \end{matrix}

Lemma 2.5 LI reduces to UST CON(poly)

Proof:

LI_{i}(G) = ⋁_{j=i+1}^{n} (i is connected to j in G).

So LI is a simple monotone formula over connectivity problems, and by lemmas 2.1, 2.3 LI reduces to UST CON. This is, actually, a monotone reduction.

Using the spanning forest and the LI function we can exactly compute the number of connected components of G, i.e.: given G we can compute a function NCC_{i} which is 1 iff there are exactly i connected components in G.

Definition 2.4 NCC(G) ↦ {0, 1}^{n}

NCC_{i}(G) = \{ \begin{matrix}1 & there are exactly i connected components in G \\ 0 & otherwise \end{matrix}

Lemma 2.6 NCC reduces to UST CON(poly)

Proof:

Let F be a spanning forest of G. It is easy to see that if G has k connected components then |F | = n − k.

Define:

\begin{matrix}f(G) = Sort ∘ LI(G) \\ g(G) = Sort ∘ SF (G). \end{matrix}

Then:

\begin{aligned}f_{i}(G) = 1 & ⟹ k < i \\ g_{i}(G) = 1 & ⟹ n − k < i & ⟹ k > n − i. \end{aligned}

and thus: NCC_{i}(G) = f_{i+1}(G) ∧ g_{n−i+1}(G)

Therefore applying lemmas 2.1, 2.2, 2.3, 2.4, 2.5 proves the lemma.

Finally we can reduce the non-connectivity problem to the connectivity problem, thus proving that SL = co − SL.

Lemma 2.7 \overline{UST CON} reduces to UST CON(poly)

Proof:

Given (G, s, t) define G^{+} to be the graph G ∪ {(s, t)}.

Denote by #CC(H) the number of connected components in the undirected graph H.

s is not connected to t in G  ⟺
# CC(G^{+}) = # CC(G) − 1  ⟺
⋁_{i=2,...,n} NCC_{i}(G) ∧ NCC_{i−1}(G^{+}).

Therefore applying lemmas 2.1, 2.3, 2.6 proves the lemma.

3 Extensions

Denote by L^{SL} the class of languages accepted by Logspace oracle Turing machines with oracle from SL. An oracle Turing machine has a work tape and a write-only query tape (with unlimited length) which is initialised after every query. We get:

Corollary 3.1 L^{SL} = SL.

Proof:

Let Lang be a language in L^{SL} solved by an oracle Turing machine M running in L^{SL}, and fix an input x⃗ to M.

Look at the configuration graph of M. In this graph we have query vertices with outgoing edges labelled “connected” and “not connected”. We would like to replace the edges labelled “connected” with their corresponding connectivity problems, and the edges labelled “not connected” with the connectivity problems obtained using our theorem that SL = co − SL.

However, there is a technical problem here, as the queries are determined by the edges and not by the query vertices. We can fix this difficulty by splitting each query vertex to its “yes” and “no” answers, and splitting each edge entering a query vertex to “connected” and “not connected” edges. Now we can easily replace each edge with a connectivity problem, obtaining an undirected graph which is st connected iff x⃗ ∈ Lang, and therefore Lang ∈ SL.

As can easily be seen the above argument applies to any undirected graph with UST CON query vertices, thus, if we carefully define SL^{SL} (see [RST82]) we get that:

Corollary 3.2 SL^{SL} = SL.

In particular, the “symmetric Logspace hierarchy” defined in [Rei82] collapses to SL.

4 Acknowledgements

We would like to thank Amos Beimel, Allan Borodin, Robert Szelepcsényi, Assaf Schuster and Avi Wigderson for helpful discussions.

References

[AKL^{+}79] R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, and C. Rackoff. Random walks, universal sequences and the complexity of maze problems. In Proceedings of the 20th Annual IEEE Symposium on the Foundations of Computer Science, 1979.

[AKS83] M. Ajtai, J. Komlos, and E. Szemeredi. An O(n log n) sorting network. In Proc. 15th ACM Symposium on Theory of Computing (STOC), pages 1–9, 1983.

[BCD^{+}89] A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3):559–578, 1989.

[GS91] Grigni and Sipser. Monotone separation of logspace from nc^{1}. In Annual Conference on Structure in Complexity Theory, 1991.

[Imm88] Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17, 1988.

[KW88] M. Karchmer and A. Wigderson. Monotone circuits for connectivity require superlogarithmic depth. In Proc. 20th ACM Symposium on Theory of Computing (STOC), pages 539–550, 1988.

[KW93] Karchmer and Wigderson. On span programs. In Annual Conference on Structure in Complexity Theory, 1993.

[LP82] Lewis and Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19, 1982.

[Nis92] N. Nisan. RL ⊆ SC. In Proc. 24th ACM Symposium on Theory of Computing (STOC), pages 619–623, 1992.

[NSW92] N. Nisan, E. Szemeredi, and A. Wigderson. Undirected connectivity in O(log^{1.5}n) space. In Proc. 33th IEEE Symposium on Foundations of Computer Science (FOCS), pages 24–29, 1992.

[Raz91] A. Razborov. Lower bounds for deterministic and nondeterministic branching programs. In Proceedings of the 8th FCT, Lecture Notes in Computer Science, 529, pages 47–60, New York/Berlin, 1991. Springer-Verlag.

[Rei82] J. H. Reif. Symmetric complementation. In Proc. 14th ACM Symposium on Theory of Computing (STOC), pages 201–214, 1982.

[RST82] W. L. Ruzzo, J. Simon, and M. Tompa. Space-bounded hierarchies and probabilistic computations. In Proc. 14th ACM Symposium on Theory of Computing (STOC), pages 215–223, 1982.

[SV85] Skyum and Valiant. A complexity theory based on boolean algebra. Journal of the ACM, 1985.

[Sze88] Szelepcsenyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26, 1988.

Recent Publications in the BRICS Report Series

RS-94-31 Noam Nisan and Amnon Ta-Shma. Symmetric Logspace is Closed Under Complement. September 1994. 8 pp.

RS-94-30 Thore Husfeldt. Fully Dynamic Transitive Closure in Plane Dags with one Source and one Sink. September 1994. 26 pp.

RS-94-29 Ronald Cramer and Ivan Damg� ard. Secure Signature Schemes Based on Interactive Protocols. September 1994. 24 pp.

RS-94-28 Oded Goldreich. Probabilistic Proof Systems. September 1994. 19 pp.

RS-94-27 Torben Bra� uner. A Model of Intuitionistic Af�ne Logic from Stable Domain Theory (Revised and Expanded Version). September 1994. 19 pp. Full version of paper appearing in: ICALP ’94, LNCS 820, 1994.

RS-94-26 S�ren Riis. Count(q) versus the Pigeon-Hole Principle. August 1994. 3 pp.

RS-94-25 S�ren Riis. Bootstrapping the Primitive Recursive Functions by 47 Colors. August 1994. 5 pp.

RS-94-24 S�ren Riis. A Fractal which violates the Axiom of Determinacy. August 1994. 3 pp.

RS-94-23 S�ren Riis. Finitisation in Bounded Arithmetic. August 1994. 31 pp.

RS-94-22 Torben Bra� uner. A General Adequacy Result for a Linear Functional Language. August 1994. 39 pp. Presented at MFPS ’94.

RS-94-21 S�ren Riis. Count(q) does not imply Count(p). July 1994. 55 pp.

RS-94-20 Peter D. Mosses and Mart��n Musicante. An Action Semantics for ML Concurrency Primitives. July 1994. 21 pp. To appear in Proc. FME ’94 (Formal Methods Europe, Symposium on Industrial Bene�t of Formal Methods), LNCS, 1994.