Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$

I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}$ are both in NL, where $st-CONN = \{\langle G,s,t \rangle \,:\, \text{there is a path from $s$ to $t$ in $G$} \}$.

Would appreciate any help

  • $\begingroup$ Any strongly connected component $C$ is uniquely represented by the vertex $x\in C$ that has the smallest numerical label. Show that you can recognize such vertices in NL, and then you can just count them in increasing order. $\endgroup$ – Emil Jeřábek Jun 17 at 15:22

Ask the prover to give you any node from $k$ distinct connected components.

You have only to verify that the nodes are not in the same connected components (hence, they are in $k$ different components, meaning that $\langle G, k\rangle \in K_{SCC}$)

Also, ask for the proof of $st-CON$ between any two of them.

Notice that even though the proof is gigantic, at every point in time the verifier will need to only verify a small portion of the proof: only one $st-CON$ is being processed at a time, hence the verifier can be constructed in such a way that will require only $O(\log(n))$ space.

The pseudocode for the verifier should look similar to this:

  • For every $i\neq j$ with $1\le i,j\le k$, do:
    • Take a look at the next $O(\log(n))$ bits of proof, and verify $st-CON$ for the $i$'th and the $j$'th nodes
  • $\begingroup$ As the question is stated, $k$ is not constant. It is part of the input. $\endgroup$ – Emil Jeřábek Jun 17 at 18:42
  • $\begingroup$ Oops :p I totally missed this important thing... $\endgroup$ – nir shahar Jun 17 at 19:01
  • $\begingroup$ When I think about it, since at every point in time the verifier only checks one $ST-con$ proof of size $O(\log(n))$, then the verifier can just check the proofs one by one in some predefined order, and the verifier wont use more than $O(\log(n))$ space. Yes, the proof is larger, but if I remember correctly thats allowed for as long as the verifier requires small space. $\endgroup$ – nir shahar Jun 17 at 19:15
  • $\begingroup$ This is true except for how you specify which $k$ nodes you want to show are in different components. This will take $O(k\log(n))$ memory, which is not logarithmic in the size of $k$... $\endgroup$ – nir shahar Jun 17 at 19:23
  • $\begingroup$ The definition of NL does not allow you to generate a polynomial-size “proof” and subsequently verify it in logarithmic space. This would in fact give you all of NP. See my comment below the question how to do this correctly. $\endgroup$ – Emil Jeřábek Jun 17 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.