## About Undirected ST connectivity in log-space WoW it was hard!

### July 18, 2008

During my final days as an undergraduate student , our computational theory professor assigned to us an open project which is discussing any interesting area for each one in the computational theory …

It was a hard choice , alot of difficult topics , you may know nothing about each of them .. just interesting names..

I was studying space complexity classes , when I found a topic seemed to be interesting .. ( Undirected ST connectivity in log-space ) proving that the class **L** ( log space ) equivalent to the class **SL** ( symmetric log space ).

Really I didn’t understand anything…Although my project’s buddy **mahmoud** and I , decided to take this as a challenge. and make it our major project..

**Symmetric log space** .. What is this .. **Expanders** WoW .. **Rotational Maps** .. **ZigZag products. **

What the hell is this! .. however, we started working and we found it really interesting..

Let’s talk seriously now..

**ST-connectivity **known as ( **ST-CON ) **is one of the most famous problems in space computational complexity .. It is the problem of deciding whether there is a path between node S and node T in a graph . This problem is complete under **NL** (Non- deterministic logarithmic space complexity ) . So solving this problem in log space complexity is a major riddle .. The result will be proving that **L = NL **equivalent in time complexity that **P = NP . **

The **Undirected ST-connectivity **is the version of **ST-connectivity **where the graph is undirected. known as

( **U-STCON)**

Scientists saw **(U-STCON) **is mainly simpler than the directed version .. It was an area of interest for researchers for more than 2 decades.

(**U-STCON ) **defines a turning machine , called **Symmetric turing machine **.. defining the **symmetric log space class ( SL )**

SL was first defined in 1982 by Lewis and Papadimitriou1, who were looking for a class

in which to place USTCON, which until this time could, at best, be placed only in NL,

despite seeming not to require nondeterminism. They defined the symmetric Turing

machine, used it to define SL. Symmetric Turing machines are kind of Turing machines

with limited nondeterministic power. Informally Symmetric computations are reversible

in an approximate manner. A symmetric computation is divided into locally

deterministic sub computation ( segments ) between special configuration , where

nondeterminism takes place , such that the only special configuration reached from a

backward computation is the special configuration started the segment. Thus the

segments are locally deterministic in its forward direction and have limited

nondeterminism in its backward direction . Also if there is a way from special

configuration A1 to special configuration A2 , there must be a way back from A2 to A1.

undirected connectivity was one of the most appealing examples of the computa tional power of randomness. Whereas every graph (e.g., a planar graph representing a maze) can be efficiently traversed by a deterministic algorithm, the classical deterministic algorithms required an extensive use of (extra) memory (i.e., linear in the size of the graph). On the other hand, it was known that, with high probability, a random walk (of polynomial length) visits all vertices in the corresponding connected component. Thus, the randomized algorithm requires a minimal amount of auxiliary memory (i.e., logarithmic in the size of the graph). Even after more than a decade of focused attension at the issue, a significant gap remained between the space complexity of randomized and deterministic polynomialtime algorithms for this natural and ubiquitous problem. Undirected connectivity became the most famous example where randomized computations seemed more powerful than deterministic ones.

Omer Reingold presented his recent breakthrough result as serting that any graph can be traversed by a deterministic polynomialtime algo rithm that only uses a logarithmic amount of auxiliary memory. His algorithm is based on a novel approach that departs from previous attempts, where the latter tried to derandomize the randomwalk algorithm. Instead, Reingold’s algorithm traverses a virtual graph, which (being an “expander”) is easy to traverse (in deterministic logarithmicspace), and maps the virtual traversal of the virtual graph to a real

traversal of the actual input graph. The virtual graph is constructed in (logarithmically many iterations, where in each iteration the graph becomes easier to traverse.

Here We will Present the USTCON problem and overview of the efforts done in solving it , and we will present **Omer Reingold** Deterministic Logarithmic Space Algorithm , Proving That

**L = SL**

Attached is the rest of the research made about this topic , and and explaining presentation

Here is the Explaining presentation

Hope this will be helpful

Tagged: Computational theory, Expanders, L = SL, L=SL, Omer Reingold, SL, Symmetric Log-Space, Zig-Zag products

August 9, 2008 at 7:15 am

Thanks! Really funny. I wish i could spend my time on writing articles…just have no time for it.

August 18, 2008 at 7:20 am

Interesting article 🙂

Just a quick note, NL means “non deterministic logarithmic space complexity”.

August 18, 2008 at 7:31 am

thanks

thats my bad , I’ll fix it 🙂