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

13

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 ANOTHER END OF THE LINE ( AEOL), em que o argumento é aplicado apenas a gráficos com graus internos e externos 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 ANOTHER UNBALANCED VERTEX ( AUV ): que são dados dois circuitos polinomial porte S e P que obter x{0,1}n e retorne uma lista polinomial de outros elementos em {0,1}n . Esses circuitos definem um gráfico direcionadoG=(V,E) ondeV={0,1}n e(x,y)E(yS(x)xP(y)) . O problema da busca é o seguinte: dadaS ,P ezV tal queindegree(z)outdegree(z) , encontrar outro vértice com a mesma propriedade.

Problema de pesquisa 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 AUV redutível a 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 .±kk±1AEOLAUV

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 eAEOLAUVgf1g(x,f(x))xAUVgx para y umay 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(y1)=g(y2)y1y2y2y1AUV

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

Daniil Musatov
fonte
2
"por que essas noções são equivalentes?" Pelas razões apresentadas na prova do Teorema 1 na página 505 de Christos Papadimitriou. (Caso contrário, o que você acha que é um argumento de paridade para a totalidade do AUV?) Sua definição de redutibilidade parece muito forte - por exemplo, na sua definição, expandir o conjunto de soluções pode tornar um problema total de pesquisa estritamente mais difícil.
2
+1 e -1 têm a mesma paridade. (Essa paridade é "ímpar".)O caminho certo "implica "em vez de" iff g (g(x,y) ".g(y)
2
Agora, o que nós não temos é que, eu vou chamá-lo UnbalancedInOtherDirectionVertex, que problema se reduz a PPADS , já que um pode virar as bordas se necessário para tornar o dado vértice têm maior out-grau do que em graus e, em seguida, o total de Os vértices -degree-1 em que o vértice determinado é transformado serão todos fontes e não sumidouros. Não vejo nenhuma maneira semelhante de passar do seu problema para a AEOL. k
1
Pelo menos a redução mostra que AUV é equivalente ao seu caso em que todos os vértices têm grau de indegree e outgree no máximo 1, exceto possivelmente para o vértice fornecido z, que tem indegree 0, mas pode ter um outdegree grande.
Emil Jeřábek 3.0 8/17
2
Acabei de ouvir de Frederic Meunier que ele também observou esse problema há cinco anos e Papadimitriou concordou.
domotorp

Respostas:

4

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 .G1XGvX

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|XX

s=|X|2k2sG=(V,E)2kVA,BV(A,B)EA={a0,,a2k1}B={b0,,b2k1}(ai,bi)Ei<2k

G1AVGAAX1

At=|AX|0<t2kt=2k=|A|AX(s2k)p(ab)b+(ab)=apk, 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 .(s2k)[0,(ab))b[0,a)2kXt=2k1

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<2k tXA| AX| =tAXAX(st)tXA|AX|=tAXAX

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 pppp

AUV - : dado um gráfico direcionado e um vértice cujo balanço de graus é , encontre outro desses vértices.GpG0(modp)

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

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

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

MEOL está em PPA - para cada prime .ppp

Emil Jeřábek 3.0
fonte
Gosto muito da resposta e decidi aceitá-la (é claro, respostas mais completas ainda são bem-vindas). Eu só acho que a classe representada por AUV - deve ser chamada PPAD - . Papadimitriou escreve sobre gráficos bipartidos não direcionados e apenas graus, não saldos. ppp
Daniil Musatov 15/02
3
As classes são generalizações do PPA, não do PPAD, para . Papadimitriou apresenta um problema completo diferente do AUV- (observe que seus gráficos são bipartidos), mas é equivalente à minha definição. Todo o esquema de nomes é terrivelmente confuso; o uso de gráficos direcionados x não direcionados para uma classe específica é apenas um acidente, muitas das classes têm problemas completos em relação aos gráficos direcionados e não direcionados (como no caso do PPA- ). Além disso, apesar de seus nomes, a maioria das classes não se baseia em argumentos de paridade, mas em outros princípios de contagem. Somente o PPA é sobre paridade. p pp=2pp
Emil Jeřábek 3,0
Obrigado, entendi. É de fato a mesma classe. Ouvi uma especulação de que Papadimitriou escolheu o nome PPAD porque se parece com seu próprio sobrenome.
Daniil Musatov
Você tem uma referência para o PPAD estar no PPA-p?
Domotorp 28/02
1
Não é explícito, mas, por exemplo, o problema que define o PPAD-completo é literalmente um caso especial de AUV- . p
Emil Jeřábek 3.0