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 polynomial­time algorithms for this natural and ubiquitous problem. Undirected connectivity became the most famous example where randomized computations seemed more powerful than de­terministic ones.
Omer Reingold presented his recent breakthrough result as­ serting that any graph can be traversed by a deterministic polynomial­time 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 random­walk algorithm. Instead, Reingold’s algorithm traverses a virtual graph, which (being an “expander”) is easy to traverse (in deterministic logarithmic­space), 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  Report Docuement

Here is the  Explaining presentation

Hope this will be helpful

Advertisements

3 Responses to “About Undirected ST connectivity in log-space WoW it was hard!”

  1. John Davis Says:

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

  2. Gennadiy Korol Says:

    Interesting article 🙂

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

  3. moustafaemara Says:

    thanks
    thats my bad , I’ll fix it 🙂


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: