1
$\begingroup$

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:

  1. Place a mark on node s.
  2. Repeat the following until no additional nodes are marked:
  3. 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.
  4. 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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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$).

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.