Cheap and Secure Web Hosting Provider : See Now

[Solved]: Why IS is not in NL, only in NP?

, , No Comments
Problem Detail: 

All we need to do is guess $k$ vertices. We look at vertex $v_1$, and make sure $v_1$ is not connected to $v_2...v_k$. Then, we "throw" $v_1$, and look at $v_2$. We do this to all vertices.

Meaning that we only need to guess $k$ vertices, and in our working memory (which determinates NL or NP) we only need to keep 2 vertices.

Where is my mistake?

Asked By : Ran

Answered By : Ariel

First, $NL\stackrel{?}{=} NP$ is still open, so $IS\in NL$ is possible (within our current knowledge, though we believe that they are different).

The problem with your proof, is that when you "guess $k$ vertices", you have to write them in your memory (when we say "guess", we mean that we write a vertex in the working tape, where at each step our machine writes either $0$ or $1$). Keeping $k$ vertices simultaneously (where $k$ is part of the input), requires more than logarithmic space.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback