Faz

15

O que acontece se definirmos P P A DPPAD de tal modo que em vez de um circuito polytime Turing-máquina / polysize, um logspace Turing-máquina ou um A C 0AC0 circuito codifica o problema?

Recentemente dando algoritmos mais rápidos para Circuit satisfiability para pequenos circuitos acabou por ser importante, então eu pergunto o que acontece com as versões rectricted de P P A DPPAD .

domotorp
fonte
Buss e Johnson, "Provas proposicionais e reduções entre problemas de pesquisa NP", provam que o PPAD está fechado em reduções de Turing, e tenho certeza de que uma pequena modificação do argumento fornece a equivalência do PPAD à sua versão (uniforme) AC ^ 0 .
Emil Jeřábek apoia Monica
@Emil: Obrigado pela sugestão, infelizmente as noções deste artigo estão além de mim. Ficaria muito grato se alguém pudesse me dizer suas implicações. Além disso, deixe-me conectar-se a sua pré-impressão aqui: math.ucsd.edu/~sbuss/ResearchWeb/NPSearch/NPSearch.pdf
domotorp

Respostas:

10

Sim, Um C 0 P Um D = P P A DAC0PAD=PPAD . (Aqui e abaixo, eu estou supondo que A C 0AC0 é definido como uma classe uniforme. Claro que, com nonuniform A C 0AC0 que tínhamos acabado de chegar P P A D / p o l yPPAD/poly .)

A ideia básica é bastante simples: A C 0AC0 pode fazer um passo de cálculo de uma máquina de Turing, portanto, podemos simular um tempo polinomial borda calculável por um polinomial longo da linha A C 0AC0 bordas -computable. Por uma extensão adicional da idéia, pode-se simular arestas computáveis ​​em tempo poli com um oráculo do PPAD, ou seja, o PPAD é fechado sob redutibilidade de Turing; esse argumento é dado em Buss e Johnson .

Existem muitas definições equivalentes de PPAD na literatura que diferem em vários detalhes, portanto, deixe-me corrigir uma aqui por definição. Uma pesquisa NP problema SS é em PPAD se houver um polinómio p ( n )p(n) , e as funções de tempo polinomial f ( x , u )f(x,u) , g ( x , u )g(x,u) , e h ( x , u )h(x,u) com as seguintes propriedades. Para cada entrada xx de comprimento nn , ff e gg representam um gráfico direcionado G x = ( Vx , E x ) sem auto-loops em que V x = { 0 , 1 } p ( n ) , e cada nó tem dentro e fora de grau no máximo 1 . A representação é tal que, se ( u , v ) E x , em seguida, f ( x , u ) = v e g ( x , v ) = u u tem a graus 0 ,Gx=(Vx,Ex)Vx={0,1}p(n)1(u,v)Exf(x,u)=vg(x,v)=u ; E seu0 f ( x , u ) = u ; e se u possui grau 0 , g ( x , u ) = u .f(x,u)=uu0g(x,u)=u

O nó 0 p ( n )V x é uma fonte (ou seja, possui grau 0 e grau 1 ). Se u V x é qualquer fonte ou coletor (grau 1 , grau 0 ) diferente de 0 p ( n ) , então h ( x , u ) é uma solução para S ( x ) .0p(n)Vx01uVx100p(n)h(x,u)S(x)

We can define AC0PADAC0PAD similarly, except we require f,g,hf,g,h to be in FAC0FAC0.

I will ignore hh in the construction for simplicity. (It is not hard to show that one can take it to be a projection, hence AC0AC0-computable.)

So, consider a PPAD problem SS defined by ff and gg, and fix Turing machines computing ff and gg in time q(n)q(n). For any xx, we define a directed graph Gx=(Vx,Ex)Gx=(Vx,Ex) whose vertices are sequences of the following form:

  • (0,u,c1,,ck)(0,u,c1,,ck), where uVxuVx, 0kq(n)0kq(n), and c1,,ckc1,,ck are the first kk configurations in the computation of f(x,u)f(x,u).

  • (0,u,c1,,cq(n),v,d1,,dk)(0,u,c1,,cq(n),v,d1,,dk), where u,vVxu,vVx, 0kq(n)0kq(n), f(x,u)=vf(x,u)=v, c1,,cq(n)c1,,cq(n) is the full computation of f(x,u)f(x,u), and d1,,dkd1,,dk are the first kk steps in the computation of g(x,v)g(x,v).

  • (1,v,d1,,dk)(1,v,d1,,dk), where 0p(n)vVx0p(n)vVx, 0kq(n)0kq(n), and d1,,dkd1,,dk are the first kk configurations in the computation of g(x,v)g(x,v).

  • (1,v,d1,,dq(n),u,c1,,ck)(1,v,d1,,dq(n),u,c1,,ck), where u,vVxu,vVx, v0p(n)v0p(n), 0kq(n)0kq(n), g(x,v)=ug(x,v)=u, d1,,dq(n)d1,,dq(n) is the computation of g(x,v)g(x,v), and c1,,ck are the first k steps in the computation of f(x,u).

Ex consists of the edges in Vx×Vx of the following kinds:

  • (0,u,c1,,ck)(0,u,c1,,ck+1)

  • (0,u,c1,,cq(n))(0,u,c1,,cq(n),v)

  • (0,u,c1,,cq(n),v,d1,,dk)(0,u,c1,,cq(n),v,d1,,dk+1)

  • (0,u,c1,,cq(n),v,d1,,dq(n))(1,v,d1,,dq(n),u,c1,,cq(n)) if f(u)=v and g(v)=u (i.e., either (u,v)Ex, or u=v is an isolated vertex)

  • (1,v,d1,,dq(n),u,c1,,ck+1)(1,v,d1,,dq(n),u,c1,,ck)

  • (1,v,d1,,dq(n),u)(1,v,d1,,dq(n))

  • (1,v,d1,,dk+1)(1,v,d1,,dk)

  • (1,u)(0,u)

Formally, let r(n) be a polynomial bounding the lengths of binary representations of all the sequences above (such that we can extend or shorten sequences, and extract their elements with AC0-functions); we actually put Vx={0,1}r(n), and we let all vertices except the above-mentioned sequences to be isolated.

It is easy to see that the functions f, g representing Gx are AC0-computable: in particular, we can test in AC0 whether c1,,ck is a valid partial computation of f(x,u), we can compute ck+1 from ck, and we can extract the value of f(x,u) from cq(n).

The sinks in Gx are nodes of the form (0,u,c1,,cq(n),u,d1,,dq(n)) where u is a sink in Gx. Likewise, sources are (1,v,d1,,dq(n),v,c1,,cq(n)) where v is a source in Gx, except that in the special case v=0p(n), we have pruned the line early and the corresponding source in Gx is just (0,0p(n)). We can assume the encoding of sequences is done in such a way that (0,0p(n))=0r(n).

Thus, f and g define an AC0PAD problem S, and we can extract a solution to S(x) from a solution to S(x) by an AC0-function h which outputs the second component of a sequence.

Emil Jeřábek supports Monica
fonte