The end-of-the-line problem (defining problem of the PPAD class) is defined on an up to exponentially large directed graph G with no isolated vertices, with each vertex having up to one predecessor and one successor. G is given by a polynomial time function f(v) which returns the predecessor and successor of a vertex v if such exist. The problem is finding a vertex with no predecessor or successor given a vertex with no predecessor.
My question is, it seems that the problem is artificially constructed to not be solvable in polynomial time. We are saying G is exponentially large without saying with respect to what (the problem can clearly be solved in polynomial time in the number of vertices by checking every vertex). My guess for this is that this problem is meant to be a rather artificial problem and has more meaning in the context of reductions (G is exponential in terms of some parameter in the problem we are trying to reduce). Can anyone confirm or shed more light on this?
Thanks!