O que acontece se definirmos P P A D
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 D
O que acontece se definirmos P P A D
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 D
Respostas:
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)∈Ex f(x,u)=v g(x,v)=u ; E seu 0 f ( x , u ) = u ; e se u possui grau 0 , g ( x , u ) = u .f(x,u)=u u 0 g(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)∈Vx 0 1 u∈Vx 1 0 0p(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 G′x=(V′x,E′x)G′x=(V′x,E′x) whose vertices are sequences of the following form:
(0,u,c1,…,ck)(0,u,c1,…,ck) , where u∈Vxu∈Vx , 0≤k≤q(n)0≤k≤q(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,v∈Vxu,v∈Vx , 0≤k≤q(n)0≤k≤q(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)≠v∈Vx0p(n)≠v∈Vx , 0≤k≤q(n)0≤k≤q(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,v∈Vxu,v∈Vx , v≠0p(n)v≠0p(n) , 0≤k≤q(n)0≤k≤q(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).
E′x consists of the edges in V′x×V′x 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 V′x={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 G′x 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 G′x 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 G′x 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.
fonte