Help making the distinction between polynomial and exponential time I'm trying to understand how problems are categorized in these two classes. I have a specific problem I'm looking at, the directed path problem: PATH = $\{\langle G,s,t \rangle | G$ is a directed graph that has a directed path from $s$ to $t$$\}$. The algorithm that's said to run in polynomial time is described as follows:


*

*Place a mark on node $s$

*Repeat the following until no additional nodes are marked: 

*Scan all the edges of $G$. If an edge $(a,b)$ is found going from a marked node $a$ to an unmarked node $b$, mark node $b$.

*If $t$ is marked, $accept$. Otherwise, $reject$.
I'm just having trouble understanding how this runs in polynomial time and why it runs in polynomial time. Because it seems like this would be no different than a brute-force search which actually runs exponential.
Any clarification on the problem would be highly appreciated.
 A: There are at most $N^2$ edges in a directed graph on $N$ vertices (think in terms of an adjacency matrix), so each iteration of the loop takes $O(N^2)$ time to scan all the edges and at each edge check if the endpoint of the edge is marked (the check for marked-ness/marking a node is $O(1)$ ). Each iteration must mark at least one more node to continue, so there are at most $N$ iterations (since there are $N$ nodes), so the overall algorithm is at most $O(N^3)$ with the final check for $t$ being marked being $O(1)$. 
A: Thinking about this in terms of an adjacency list might be better. Adjacency matrices are great for examining the structure of a graph, but an adjacency list structure is generally (not always, but generally) better for algorithmic graph theory, such as path finding.
Now let's look at the algorithm in terms of pseudo-code:
$$
function doesPathExist(Digraph graph, Vertex start, Vertex end){
Hashtable markedVertices := new Hashtable
Queue vertexQueue := new Queue

add start to markedVertices
for each edge e in E(start)
    push e.other onto vertexQueue

while vertexQueue is not empty
    Vertex temp := vertexQueue.poll()
    add temp to markedVertices

    for each edge e in E(temp)
       if !vertexQueue.contains(e.other)
            push e.other onto vertexQueue

return hashtable.contains(end) 

}
$$
So let's examine the algorithm. The first for loop takes at most V-1 iterations, which is O(V). The while loop takes at most V-1 iterations, if all of the vertices are visited. The inner for loop also takes V-1 iterations. Since the inner for loop is nested in the while loop, the complexity of the while loop is $(V-1) * (V - 1) = O(V^{2})$. So our runtime complexity is $O(V) + O(V^{2}) = O(V^{2})$. 
Of course, we could optimize the algorithm some more. But hopefully this helps you see the complexity.
A: You might want to think about solving this problem with an algorithm that runs in exponential time. Recall that exponential time is $EXP = TIME(2^{n^k})$ for constant $k$, where $n$ is the size of the input. An exponential running time algorithm enters a loop over $n$, and in that loop it enters two more loops over $(n-1)$, and in those loops it enters two more loops over $(n-2)$...
An algorithm with exponential running time can be obtained by converting a non-deterministic algorithm to a deterministic algorithm. Consider the non-deterministic algorithm $N$ that decides whether a path exists from $a$ to $b$ in some graph $G$.
$N = $ "On input $\langle G,a,b \rangle$


*

*Non-deterministically select all vertices $S \in \mathcal{P}(V)$, where $V$ is the set of vertices in graph $G$.

*If $a,b \notin S$ then reject.

*If $S$ constitutes a valid path from $a$ to $b$, then accept. Otherwise reject."


Step 3 has polynomial running time (we have to check whether the nodes actually are a path from $a$ to $b$), so $N \in NTIME(n^k)$ for constant $k$, but it has at least exponential deterministic running time. Step 1 will branch exponentially in deterministic time: It requires $2^{|V|}$ branches, which is exponential in the size of the input: The input is $|G|$, which is at most $|E| + |V|$ or $|V|^2 + |V|$, because any directed graph has at most $|V|^2$ edges.
Recall that polynomial time is $P = TIME(n^k)$ for constant $k$. The algorithm you have given traverses over all edges multiple times in a BFS like manner, which has running time $O(|E|) = O(|V|^2)$ or $O(n^2) \in TIME(n^k) = P$. It is essentially a BFS where $\Omega(n^2) = O(n^2)$ (best case running time is equal to worst case running time).
A: Be careful. Complexity people tend to talk loosely about "polynomial" to mean that the function is bounded by a polynomial, essentially bounded by a power of $n$, and "exponential" to mean functions that are not bounded by a polynomial. Cases in point are $c^n$, but also $n!$ or $e^{n^2}$, both of the last two grow even faster than exponential. But there are also functions like $n^{\log n}$ in this bunch, this one grows faster than any fixed power of $n$ (the exponent grows) but slower than $c^n$ for any $c > 1$ (compare their logarithms when $n \to \infty$)
