I am reading Sipser's Introduction to the Theory of Computation, and have trouble understanding the difference between polynomial and non-polynomial problems. When describing a PATH problem, where
PATH = {(G, s, t)| G is a directed graph that has a directed path from s to t}
the author says that using a BFS algorithm to this problem is polynomial. The algorithm is as follows:
M = "On input (G, s, t), where G is a directed graph with nodes s and t:
- 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."
In the next example, the author described a problem of determining whether 2 numbers are relatively prime, where
RELPRIME = {(x, y) | x and y are relatively prime}.
The author argues that if we iterate from 1 to min(n, k), and check if each number divides both x and y, the algorithm would be exponential because
the magnitude of a number represented in binary, or in any other base k notation for k ≥ 2, is exponential in the length of its representation.
Why doesn't the same argument aply to the PATH problem? The nodes have to be indexed and would have to be represented using the same representation, so why isn't this algorithm exponential as well? What about iterating from 1 to n, and printing each number, is that also an exponential algorithm?
Thanks
1 Answer 1
If the input is an integer $n$, then one needs logarithmic space $\log n$ to store it, using its binary decomposition.
An algorithm of time complexity $\mathcal{O}(n)$ would then be exponential, since $n$ is exponential in $\log n$.
On the other hand, though there are different ways to represent a graphe $G = (V, E)$, the most usual one is as an array (or hashtable) of length $|V|$, such that $G[v]$ contains a list (or set) of the neighbors of $v$.
The array itself needs space $\mathcal{O}(|V|)$, and the lists need space $\sum\limits_{v\in V}\deg(v) = \mathcal{O}(|E|)$.
Actually, one could consider that this requires a space $\mathcal{O}(|E|\log |V|)$, since each neighbor needs a space $\mathcal{O}(\log |V|)$ to be stored. However, this does not change that much the complexity analysis.
Overall, one needs space $\mathcal{O}(|V| + |E|)$ to store the graph, hence a graph traversal has complexity linear in the size of the input.
Note that there are some representations of a graph such that a graph traversal could be exponential in the size of the input. For example, one could represent a graph $G = (V, E)$ using a boolean formula $\varphi$ over 2ドル\log_2 |V|$ variables such that $\{s,t\}\in E$ if and only if $\varphi(s_0,s_1,...,s_{n-1},t_0,t_1,...,t_{n-1}) = 1$, where $(s_{n-1}s_{n-2}...s_1s_0)_2$ is the binary representation of $s$ (and same thing for $t$).