<p>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 <a href="https://arxiv.org/abs/2205.02168" rel="nofollow noreferrer">Separations in Proof Complexity and TFNP</a>.</p>

CC BY-SA 4.0
2023-02-21T10:05:23.987Z
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.)
Emil Jeřábek
CC BY-SA 4.0
2023-02-21T20:22:43.987Z
You are right, the problem is only mentioned in the 1994 paper on the last but one page, under para (5).
domotorp
CC BY-SA 4.0
2023-02-21T09:29:46.603Z
2023-02-21T09:29:46.603Z
domotorp
<p>The END OF THE LINE problem is stated as</p>
<blockquote>
<p>Given two circuits, P and N, a node, v, is balanced if <span class="math-container">$P(N(v)) = N(P(v)) = v$</span> or <span class="math-container">$P(N(v)) \neq N(P(v)) \neq v$</span>. Given that <span class="math-container">$0^n$</span> is not balanced, find another node that is not balanced.</p>
</blockquote>
<p>I was wondering if this modification is also PPAD-complete, as END OF THE LINE is:</p>
<blockquote>
<p>Given that <span class="math-container">$0^n$</span> has in-degree 0 and out-degree 1, find a node that has in-degree 1 and out-degree 0.</p>
</blockquote>
<p>Of course, this is also equivalent to something like</p>
<blockquote>
<p>Given that <span class="math-container">$0^n$</span> has in-degree 1 and out-degree 0, find a node that has in-degree 0 and out-degree 1.</p>
</blockquote>
<p>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.</p>
<p>What is known about these problems, if anything?</p>

<cc.complexity-theory><graph-theory><np><ppad>
END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node
wavosa
# END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node

(Asked by: username_0 on 2023-02-20)

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?

**Tags:** cc.complexity-theory, graph-theory, np, ppad

---

## 1 answers

### Answer by username_1 on 2023-02-21. Score: 4 | Accepted answer

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](https://arxiv.org/abs/2205.02168).

> **Comments:**
> **username_2**: 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.)  
> **username_1**: You are right, the problem is only mentioned in the 1994 paper on the last but one page, under para (5).  

---

