Famous PPAD class of problems is formally defined by specifying one of its complete problems, known as End-Of-The-Line:
End-Of-The-Line Problem: $G$ is a (possibly exponentially large) directed graph with no isolated vertices, and with every vertex having at most one predecessor and one successor. $G$ is specified by giving a polynomial-time computable function $f(v)$ (polynomial in the size of $v$) that returns the predecessor and successor (if they exist) of the vertex $v$. Given a vertex $s$ in $G$ with no predecessor, find a vertex $t≠s$ with no predecessor or no successor. (The input to the problem is the source vertex s and the function $f(v)$). In other words, we want any source or sink of the directed graph other than $s$.
Let's consider the slightly augmented version of End-Of-The-Line problem.
End-Of-The-Line Augmented Problem: The definition is same as for End-Of-The-Line expect that it's required to find not a vertex $t≠s$ with no predecessor or no successor, but the exact end of the path of the given source vertex $s$.
Intuitively, it seems like End-Of-The-Line Augmented Problem is not more in PPAD, just because it requires something more stronger than End-Of-The-Line Problem. How to show that End-Of-The-Line Augmented Problem is NP-hard?
