Apakah

Apa yang terjadi jika kita mendefinisikan ${\bf PPAD}$ sehingga bukan sirkuit polytime Turing-mesin / polysize, sebuah logspace Turing-mesin atau ${\bf AC^0}$ sirkuit mengkodekan masalah?

Baru-baru ini memberikan algoritma cepat untuk Circuit satisfiability untuk sirkuit kecil ternyata menjadi penting, jadi saya ingin tahu apa yang terjadi pada versi rectricted dari ${\bf PPAD}$ .

$\def\ac{\mathrm{AC}^0}$Ya, $\ac\mathrm{PAD}=\mathrm{PPAD}$ . (Di sini dan di bawah, saya mengasumsikan $\ac$ didefinisikan sebagai kelas seragam. Tentu saja, dengan A C 0 yang tidak seragam, $\ac$kami hanya akan mendapatkan $\mathrm{PPAD/poly}$ .)

Ide dasarnya cukup sederhana: $\ac$ dapat melakukan satu langkah dari Turing mesin perhitungan, maka kita dapat mensimulasikan satu waktu polinomial tepi dihitung oleh garis polynomially panjang $\ac$ tepi -computable. Dengan perluasan lebih lanjut dari ide tersebut, orang dapat mensimulasikan tepi yang dapat dihitung dalam waktu poli dengan oracle PPAD, yaitu, PPAD ditutup di bawah Turing reducibilitas; argumen ini diberikan dalam Buss dan Johnson .

Ada banyak definisi setara PPAD dalam literatur yang berbeda dalam berbagai detail, oleh karena itu izinkan saya memperbaikinya di sini untuk definisi. Masalah pencarian NP $S$ ada dalam PPAD jika ada fungsi polinom $p(n)$ , dan waktu polinomial $f(x,u)$ , $g(x,u)$ , dan $h(x,u)$ dengan properti berikut. Untuk setiap input $x$ panjang n x = ( V x , E $n$ , $f$ dan $g$ merupakan grafik berarah $G_x=(V_x,E_x)$ tanpa loop otomatis di mana$V_x=\{0,1\}^{p(n)}$ , dan setiap node memiliki derajat paling tinggi dan paling luar$1$ . Representasi sedemikian rupa sehingga jika$(u,v)\in E_x$ , maka$f(x,u)=v$ dan g ( x , v ) = u ; jikau memiliki derajat 0 , f ( x , u ) = u ; dan jika$g(x,v)=u$$u$$0$$f(x,u)=u$ Anda memiliki derajat 0 , g ( x , u ) = u .$u$$0$$g(x,u)=u$

Node 0 p ( n ) ∈ V x adalah sumber (yaitu, memiliki derajat 0 dan derajat 1 ). Jika u ∈ V x adalah sumber atau sink (dalam derajat 1 , keluar-derajat 0 ) selain 0 p ( n ) , maka h ( x , u ) adalah solusi untuk S ( x ) .$0^{p(n)}\in V_x$$0$$1$$u\in V_x$$1$$0$$0^{p(n)}$$h(x,u)$$S(x)$

Kita dapat mendefinisikan A C 0 P A D dengan cara yang sama, kecuali kita membutuhkan f , g , h untuk berada dalam F A C 0 .$\ac\mathrm{PAD}$$f,g,h$$\mathrm{FAC}^0$

Saya akan mengabaikan h dalam konstruksi untuk kesederhanaan. (Tidak sulit untuk menunjukkan bahwa seseorang dapat menganggapnya sebagai proyeksi, karenanya A C 0 -computable.)$h$$\ac$

Jadi, pertimbangkan masalah PPAD S yang didefinisikan oleh f dan g , dan perbaiki mesin Turing yang menghitung f dan g dalam waktu q ( n ) . Untuk setiap x , kita mendefinisikan grafik berarah G ′ x = ( V ′ x , E ′ x ) yang simpulnya adalah urutan dari bentuk berikut:$S$$f$$g$$f$$g$$q(n)$$x$$G'_x=(V'_x,E'_x)$

• ( 0 , u , c 1 , … , c k ) , di mana u ∈ V x , 0 ≤ k ≤ q ( n ) , dan c 1 , … , c k adalahkonfigurasi k pertamadalam perhitungan f ( x , kamu ) .$(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 ) , di mana 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$ n ) adalah perhitungan penuh dari$c_1,\dots,c_{q(n)}$$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.