Czy

Co się stanie, jeśli zdefiniujemy ${\bf PPAD}$ taki sposób, że zamiast polytime-maszyny Turinga / obwodu polisize, maszyny logistycznej Turinga lub obwodu ${\bf AC^0}$ koduje problem?

Ostatnio dając szybsze algorytmy Okręgowego spełnialności dla małych obwodów okazało się być ważne, więc zastanawiam się, co się dzieje z rectricted wersjach ${\bf PPAD}$ .

$\def\ac{\mathrm{AC}^0}$Tak C 0 P D = P P D . (Tu i poniżej, m zakładając C 0 definiuje się jako jednolity klasy. Oczywiście, z niejednorodnym C 0 chcemy po prostu P P A D / s O l y ).$\ac\mathrm{PAD}=\mathrm{PPAD}$$\ac$$\ac$$\mathrm{PPAD/poly}$

Podstawowa idea jest bardzo prosta: C 0 może zrobić jeden krok w obliczeniach maszyna Turinga, stąd możemy symulować jeden wielomian czasie obliczalny przewagę przez wielomianowo długiej linii C 0 -computable krawędziach. Poprzez dalsze rozszerzenie pomysłu można symulować krawędzie obliczalne w czasie wieloczłonowym z wyrocznią PPAD, to znaczy, że PPAD jest zamknięty w warunkach redukowalności Turinga; ten argument podano w Buss i Johnson .$\ac$$\ac$

W literaturze istnieje wiele równoważnych definicji PPAD, które różnią się w różnych szczegółach, dlatego pozwolę sobie tutaj poprawić jedną z nich dla pewności. Problem wyszukiwania NP S występuje w PPAD, jeśli występuje funkcja wielomianowa p ( n ) i funkcje wielomianowe f ( x , u ) , g ( x , u ) i h ( x , u ) o następujących właściwościach. Dla każdego wejścia x długości n , f i g oznaczają skierowany wykres $S$$p(n)$$f(x,u)$$g(x,u)$$h(x,u)$$x$$n$$f$$g$x = ( V x , E x ) bez pętli własnych, gdzie V x = { 0 , 1 } p ( n ) , a każdy węzeł ma stopień i stopień co najwyżej 1 . Odwzorowanie jest taka, że w przypadku ( u , v ) ∈ e x , a f ( x , w kształcie U ) = v i g ( x , v ) = u ; gdyby$G_x=(V_x,E_x)$$V_x=\{0,1\}^{p(n)}$$1$$(u,v)\in E_x$$f(x,u)=v$$g(x,v)=u$u ma stopień 0 , f ( x , u ) = u ; a jeśli u ma stopień 0 , g ( x , u ) = u .$u$$0$$f(x,u)=u$$u$$0$$g(x,u)=u$

Węzeł 0 p ( n ) ∈ V x jest źródłem (tj. Ma stopień 0 i stopień 1 ). Jeśli u ∈ V x jest dowolnym źródłem lub ujściem (stopień 1 , stopień 0 ) innym niż 0 p ( n ) , wówczas h ( x , u ) jest rozwiązaniem dla S ( x ) .$0^{p(n)}\in V_x$$0$$1$$u\in V_x$$1$$0$$0^{p(n)}$$h(x,u)$$S(x)$

Możemy zdefiniować A C 0 P A D podobnie, z tym że wymagamy, aby f , g , h znajdowały się w F A C 0 .$\ac\mathrm{PAD}$$f,g,h$$\mathrm{FAC}^0$

Dla uproszczenia zignoruję h w konstrukcji. (Nietrudno wykazać, że można to uznać za projekcję, stąd obliczenie A C 0 ).$h$$\ac$

Rozważmy więc problem PPAD S zdefiniowany przez f i g , i naprawimy maszyny Turinga obliczające f i g w czasie q ( n ) . Dla dowolnego x definiujemy ukierunkowany wykres G ′ x = ( V ′ x , E ′ x ), którego wierzchołki są ciągami następującej postaci:$S$$f$$g$$f$$g$$q(n)$$x$$G'_x=(V'_x,E'_x)$

• ( 0 , u , c 1 , … , c k ) , gdzie u ∈ V x , 0 ≤ k ≤ q ( n ) , oraz c 1 , … , c k są pierwszymi k konfiguracjami w obliczeniach f ( x , u ) .$(0,u,c_1,\dots,c_k)$$u\in V_x$$0\le k\le q(n)$$c_1,\dots,c_k$$k$$f(x,u)$

• ( 0 , u , c 1 , … , c q ( n ) , v , d 1 , … , d k ) , gdzie u , v ∈ V x , 0 ≤ k ≤ q ( n ) , f ( x , u ) = v , c 1 , … , c q $(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_k)$$u,v\in V_x$$0\le k\le q(n)$$f(x,u)=v$$c_1,\dots,c_{q(n)}$ is the full computation of $f(x,u)$, and $d_1,\dots,d_k$ are the first $k$ steps in the computation of $g(x,v)$.

• $(1,v,d_1,\dots,d_k)$, where $0^{p(n)}\ne v\in V_x$, $0\le k\le q(n)$, and $d_1,\dots,d_k$ are the first $k$ configurations in the computation of $g(x,v)$.

• $(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_k)$, where $u,v\in V_x$, $v\ne0^{p(n)}$, $0\le k\le q(n)$, $g(x,v)=u$, $d_1,\dots,d_{q(n)}$ is the computation of $g(x,v)$, and $c_1,\dots,c_k$ are the first $k$ steps in the computation of $f(x,u)$.

$E'_x$ consists of the edges in $V'_x\times V'_x$ of the following kinds:

• $(0,u,c_1,\dots,c_k)\to(0,u,c_1,\dots,c_{k+1})$

• $(0,u,c_1,\dots,c_{q(n)})\to(0,u,c_1,\dots,c_{q(n)},v)$

• $(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_k)\to(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_{k+1})$

• $(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_{q(n)})\to(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_{q(n)})$ if $f(u)=v$ and $g(v)=u$ (i.e., either $(u,v)\in E_x$, or $u=v$ is an isolated vertex)

• $(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_{k+1})\to(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_k)$

• $(1,v,d_1,\dots,d_{q(n)},u)\to(1,v,d_1,\dots,d_{q(n)})$

• $(1,v,d_1,\dots,d_{k+1})\to(1,v,d_1,\dots,d_k)$

• $(1,u)\to(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 $\ac$-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 $\ac$-computable: in particular, we can test in $\ac$ whether $c_1,\dots,c_k$ is a valid partial computation of $f(x,u)$, we can compute $c_{k+1}$ from $c_k$, and we can extract the value of $f(x,u)$ from $c_{q(n)}$.

The sinks in $G'_x$ are nodes of the form $(0,u,c_1,\dots,c_{q(n)},u,d_1,\dots,d_{q(n)})$ where $u$ is a sink in $G_x$. Likewise, sources are $(1,v,d_1,\dots,d_{q(n)},v,c_1,\dots,c_{q(n)})$ where $v$ is a source in $G_x$, except that in the special case $v=0^{p(n)}$, we have pruned the line early and the corresponding source in $G'_x$ is just $(0,0^{p(n)})$. We can assume the encoding of sequences is done in such a way that $(0,0^{p(n)})=0^{r(n)}$.

Thus, $f'$ and $g'$ define an $\ac\mathrm{PAD}$ problem $S'$, and we can extract a solution to $S(x)$ from a solution to $S'(x)$ by an $\ac$-function $h'$ which outputs the second component of a sequence.