3
$\begingroup$

The END OF THE LINE problem is stated as

Given two circuits, P and N, a node, v, is balanced if $P(N(v)) = N(P(v)) = v$ or $P(N(v)) \neq N(P(v)) \neq v$. Given that $0^n$ is not balanced, find another node that is not balanced.

I was wondering if this modification is also PPAD-complete, as END OF THE LINE is:

Given that $0^n$ has in-degree 0 and out-degree 1, find a node that has in-degree 1 and out-degree 0.

Of course, this is also equivalent to something like

Given that $0^n$ has in-degree 1 and out-degree 0, find a node that has in-degree 0 and out-degree 1.

These problems are at least as hard as END OF THE LINE; take example 1. Finding a node that has in-degree 1 and out-degree 0 is still finding an imbalanced node. However, there can be imbalanced nodes that don't satisfy this property.

What is known about these problems, if anything?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

This class was defined in Papadimitriou's original 1994 paper, that also introduced the class PPAD, and it is known as PPADS. There is an oracle separation between the two classes. For a recent paper on the topic, see Separations in Proof Complexity and TFNP.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I can’t find it in the 1994 paper. The first explicit reference to PPADS that I know of is Beame, Cook, Edmonds, Impagliazzo, Pitassi, The relative complexity of NP search problems (1995), where they write “the class PPADS is called PSK in [Pap90], where it is incorrectly said to be equivalent to PPAD”. ([Pap90] is Papadimitriou’s 1990 paper On graph-theoretic lemmata and complexity classes that I have no access to.) $\endgroup$
    – Emil Jeřábek
    Feb 21 at 10:05
  • 1
    $\begingroup$ You are right, the problem is only mentioned in the 1994 paper on the last but one page, under para (5). $\endgroup$
    – domotorp
    Feb 21 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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