3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ OK, great, the question makes sense to me now! I think this paper, "NP-Hardness and Results Relating to PPAD", says it is NP-hard, but I didn't look closely yet. $\endgroup$ – usul Apr 28 '13 at 6:22
  • $\begingroup$ @usul, thank you for the reference, the paper is slightly cumbersome, I have another hint: The task is actually identifying the final configuration of TM with one property is should be reversible, such that we would trace it in backward direction. Still have no idea how to that it is NP-hard. $\endgroup$ – com May 4 '13 at 8:04
4
$\begingroup$

This question is answered in the original paper by Papadimitriou 1994 original paper (pdf). It turns out that the problem is not only NP-hard but also PSPACE-hard, this is theorem 2 on page 506.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.