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

13

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

f(x)xvtv

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?

Matthias
fonte

Respostas:

15

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.

Shiva Kintali
fonte
3
Estou com problemas para estender o argumento para o PPAD. Na prova original, novos vértices são produzidos pela combinação de pares de arestas do mesmo vértice antigo. Para o PPAD, parece natural combinar as bordas de entrada e saída. Porém, não é mais garantido que cada vértice antigo desequilibrado produza apenas um novo vértice desequilibrado. E se houver muitos deles, uma pesquisa no novo gráfico poderá retornar outro novo vértice produzido pelo mesmo vértice antigo. Isso não dá uma resposta para o problema original. Como alguém pode superar esse problema?
Daniil Musatov 02/02/19