Por que essas duas definições de PPAD são equivalentes?

A classe de complexidade PPAD é geralmente definida, afirmando que o fim da linha está completo no PPAD.

$f(x)$$x$$v$$t\ne v$

Recentemente, ouvi uma definição diferente de PPAD. Tanto quanto me lembro, foi baseado no seguinte problema.

Um gráfico direcionado (novamente especificado por uma função computável em tempo polinomial) e um nó cujo grau interno não é igual ao grau externo são dados. Encontre outro nó com esta propriedade.

Claramente, o fim de linha é um caso especial do último problema, mas o último problema é realmente mais difícil de resolver? Minha pergunta é esta:

Os dois problemas estão completos para a mesma classe de complexidade PPAD? Se sim, por que? Caso contrário, qual é a classe de complexidade resultante do segundo problema?

Para questões com o artigo citado, (e, portanto, esta resposta), consulte O PPAD realmente captura a noção de encontrar outro vértice desequilibrado?

Sim. Esses dois problemas são equivalentes e, portanto, completos para o PPAD. A redução é dada na página 505 do documento original de 1994 de Papadimitriou ( pdf ), introduzindo End of the Line . Isso é válido mesmo que o grau do gráfico seja exponencial, desde que recebamos um "algoritmo de reconhecimento de borda" e uma "função de emparelhamento". Isso também é mencionado na mesma página. A redução é dada para o PPA (a versão não direcionada do PPAD). Também pode ser estendido ao PPAD.