Let's take this algorithm as an example.$PATH$ = {$G$, s, t | $G$ is a directed graph that has a directed path from s to t }.Prove that $PATH \in P $.Ok, I know the basic algorithm is to start from node s, place a mark on it, and then look over the rest of the edges and place a mark from node s to node x if there exists a edge from node s to node x. If you place a mark on node t, then accept; otherwise, keep doing this until you run out of nodes, which implies you reject.I'm getting caught up in implementation details, really. I can most likely envision a turning machine that can do this in polynomial time, but I don't know if this is the right way to go about it,per say. In Sipser, it seems like a very hand wavy proof. When I encounter an algorithm should I first figure out a way to implement it on a reasonable Turing machine? Or is there a better way to do this. Thank you.
Confused about how to exactly determine the complexity of an Algorithm
algorithms;turing machines
To prove that an algorithm is in $P$ you basically have two options:Show how to solve it using a number of operations that is polynomial in the size of the input. This means you have to specify a Turing machine to do it, and prove that each of the operations takes a polynomial amount of time. Alternatively, you would prove that the turing machine spends a polynomial amount of steps in any non-accept/reject state.Show that your problem can be reformulated as a already-known problem previously proven to be in $P$. Here you have to prove that the reformulation is correct and that it takes polynomial time.