O PPAD realmente captura a noção de encontrar outro vértice desequilibrado?

Complexidade classe PPAD foi inventado por Christos Papadimitriou em seu seminal 1994 papel . A classe é projetada para capturar a complexidade dos problemas de pesquisa, onde a existência de uma solução é garantida pelo "argumento Paridade em gráficos direcionados": se houver um vértice desequilibrado em um gráfico direcionado, deverá existir outro. Mas geralmente a classe é formalmente definida em termos de $\mathsf{ANOTHER\ END\ OF\ THE\ LINE}$ ( $\mathsf{AEOL}$), em que o argumento é aplicado apenas a gráficos com graus internos e externos $\le 1$ . Minha pergunta é: por que essas noções são equivalentes?

Até este ponto, é uma duplicata dessa pergunta . Agora, quero declarar o problema formalmente e esclarecer por que não estou satisfeito com a resposta lá.

Pesquisar problema $\mathsf{ANOTHER\ UNBALANCED\ VERTEX}$ ( $\mathsf{AUV}$ ): que são dados dois circuitos polinomial porte $S$ e $P$ que obter $x\in\{0,1\}^n$ e retorne uma lista polinomial de outros elementos em $\{0,1\}^n$ . Esses circuitos definem um gráfico direcionado$G=(V,E)$ onde$V=\{0,1\}^n$ e$(x,y)\in E\Leftrightarrow (y\in S(x)\land x\in P(y))$ . O problema da busca é o seguinte: dada$S$ ,$P$ e$z\in V$ tal que$indegree(z)\ne outdegree(z)$ , encontrar outro vértice com a mesma propriedade.

Problema de pesquisa $\mathsf{AEOL}$ : o mesmo, mas $S$ e $P$ retornam uma lista vazia ou um elemento.

A noção de reducibilidade (corrigido de acordo com a sugestão de Ricky): total de pesquisa problema $A$ é redutível ao total de pesquisa problema $B$ através de funções polinomiais $f$ e $g$ se $y$ é uma solução de $f(x)$ na problema $B$ implica $g(x,y)$ é uma solução para $x$ no problema $A$ .

Pergunta formal : por que $\mathsf{AUV}$ redutível a $\mathsf{AEOL}$ ? Ou devemos usar outra noção de redutibilidade?

Christos Papadimitriou prova o teorema análogo sobre o PPA (Teorema 1, página 505), mas o argumento parece não funcionar para o PPAD . O motivo é que um vértice com balanço de graus será transformado em k vértices com balanço de graus ± 1 . Então o algoritmo para A E O L pode obter um desses vértices e retornar outro. Isto não iria produzir um novo vértice para um L V .$\pm k$$k$$\pm1$$\mathsf{AEOL}$$\mathsf{AUV}$

As coisas estão piorando porque em sempre há um número par de vértices desequilibrados, mas em A U V pode haver um número ímpar deles. É por isso que não se pode construir uma bijeção entre esses dois conjuntos eg nem sempre pode ser igual a f - 1 . Se g ( x , f ( x ) ) ≠ x , em seguida, obtém-se um método para a resolução de um L V em tempo polinomial, pelo menos, para alguns casos. Se g não depende de x e$\mathsf{AEOL}$$\mathsf{AUV}$$g$$f^{-1}$$g(x,f(x))\ne x$$\mathsf{AUV}$$g$$x$ para y uma ≠ y 2 , em seguida, y 2 pode ser devolvido como resposta para y 1 . Isso não daria uma solução para um U V .$g(y_1)=g(y_2)$$y_1\ne y_2$$y_2$$y_1$$\mathsf{AUV}$

Pergunta final : os obstáculos listados acima podem ser superados de alguma forma? Pode-se empregar uma possível dependência de em x ?$g$$x$

Os problemas provaram ser equivalentes (e, portanto, completos com o PPAD), consulte a Seção 8 em O problema da bola peluda é completa com o PPAD por Paul W. Goldberg e Alexandros Hollender .

Esta é uma pergunta interessante, e só posso dar uma resposta parcial.

É fácil ver que a construção na p. 505 do artigo de Papadimitriou mostra a equivalência do AUV com seu caso especial

MUITOS TERMOS DA LINHA (MEOL): Dado um gráfico direcionado com grau dentro e fora no máximo 1 (representado pelos circuitos como acima), e um conjunto X vazio de fontes de G , encontre um coletor ou uma fonte v ∉ X .$G$$1$$X$$G$$v\notin X$

Por um lado, acho difícil imaginar uma transformação desses gráficos que reduza um número maior de fontes a uma.

No entanto, por outro lado, o MEOL pertence a todas as classes comumente estudadas que contêm PPAD, exceto possivelmente o próprio PPAD :

Primeiro, obviamente,

MEOL está no PPADS .

Vou esboçar abaixo um argumento que

MEOL está em PPA

$G=(V,E)$$X$

$|X|$$X$$X$

$s=|X|$$2^k$$2$$s$$G'=(V',E')$$2^k$$V$$A,B\in V'$$(A,B)$$E'$$A=\{a_0,\dots,a_{2^k-1}\}$$B=\{b_0,\dots,b_{2^k-1}\}$$(a_i,b_i)\in E$$i<2^k$

$G'$$1$$A\in V'$$G$$A$$A\cap X\ne\varnothing$$1$

$A$$t=|A\cap X|$$0<t\le2^k$$t=2^k=|A|$$A\subseteq X$$\binom{s}{2^k}$$p$$\binom ab$$b+(a-b)=a$$p$$k$, segue que é ímpar. Além disso, existem bijections em tempo polinomial entre e subconjuntos de elementos de . Usando isto, podemos definir uma correspondência de tempo polinomial em todos, mas um dos subconjuntos -element de . Nós o incluímos no gráfico, o que reduz o número de fontes conhecidas com para .$\binom{s}{2^k}$$[0,\binom ab)$$b$$[0,a)$$2^k$$X$$t=2^k$$1$

Para , a fórmula de contagem de transporte mostra que é par. Mais uma vez, podemos encontrar uma correspondência explícita sobre subconjuntos -element de . Nós o estendemos às fontes conhecidas com aplicando a correspondência em e deixando fixo.$0<t<2^k$ tXA| A∩X| =tA∩XA∖$\binom st$$t$$X$$A$$|A\cap X|=t$$A\cap X$$A\smallsetminus X$

Dessa maneira, produzimos um gráfico não direcionado com um vértice conhecido da folha. Pedimos ao oráculo do PPA outra folha e, por construção, podemos extrair dele uma resposta para a instância do MEOL .

Conforme mencionado brevemente por Papadimitriou, podemos generalizar o PPA para as classes PPA - para qualquer primo . Um exemplo de um problema completo de PPA - ép $p$$p$$p$

AUV - : dado um gráfico direcionado e um vértice cujo balanço de graus é , encontre outro desses vértices.$p$$G$${}\not\equiv0\pmod p$

(Veja esta resposta para a equivalência de AUV - com a definição de PPA de Papadimitriou - .)$p$$p$

PPA - é apenas PPA . As classes PPA - são consideradas incomparáveis ​​em pares e incomparáveis ​​com o PPADS . Todos eles incluem PPAD .$2$$p$

Não havia nada de especial sobre no argumento que descrevi acima, e ele pode ser facilmente modificado para gerar$p=2$

MEOL está em PPA - para cada prime .$p$$p$