2
$\begingroup$

$STCON=\text{{(G,s,t)|G is a directed graph with a path from s to t}}$ $Co-STCON=\text{{(G,s,t)|G is a directed graph without a path from s to t}}$

I've tried the following proof:
Let $S\in NL$, and let $S^\complement \in coNL$. ($S^\complement$ complement is $S$)
Let $M_S$ be the NDTM that solves $S$.
$x\in S \iff x\notin S^\complement$, so If I can decide membership in $S^\complement$, I can decide membership in $S$. Then I claim that $x\in S^\complement \iff(G_x,v_0,v_{acc}) \in Co-STCON$, where $G_x$ is the configuration graph of $M_S(x)$, $v_0$ is starting configuration, and $V_{acc}$ is a single accepting configuration.

The problem I have with the proof above is that it has the form $x\in S \iff (G_x,v_0,v_{acc}) \notin Co-STCON$, so I feel like I'm missing something essential here. Is it correct?

$\endgroup$
4
$\begingroup$

Your proof doesn't work, since you're using an oracle reduction rather than a many-one reduction.

To show that a problem $A$ is NL-complete, you need to show that for every $S \in \mathsf{L}$ there is a logspace-computable function $f_S$ such that $x \in S$ iff $f_S(x) \in A$ (that's the definition); it's enough to show such a reduction for a single NL-complete problem $S$ (exercise). You show instead that $x \in S$ iff $f_S(x) \notin A$.

Showing that nonSTCON is NL-complete is actually not so easy. Even showing that nonSTCON is in NL is not so easy; it is equivalent to showing that NL equals coNL. This is a non-trivial result due to Immerman and Szelepcsényi.

$\endgroup$

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.