This question already has an answer here:

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.


marked as duplicate by David Richerby complexity-theory Jul 29 at 9:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Browse other questions tagged or ask your own question.