Given the st-connectivity problem (we need to decide if there is a directed path from s to t in a graph G: https://en.wikipedia.org/wiki/St-connectivity) we have a non-deterministic Turing machine M that guesses a path from s to t. If the current path is of size n (the number of nodes in the graph) we can terminate.

Suppose I want to decide if (G,s,t) is in the complement of st-connectivity (st-non-connectivity). I will run M with the input (G,s,t) for n steps, and accept iff M didn't reach t, thus st-non-connectivity is in NL, therefore NL=co-NL

Something here is obviously wrong, but I can't understand what exactly.


Browse other questions tagged or ask your own question.