Kompleksitas kelas PPAD (misalnya, menghitung berbagai kesetimbangan Nash) dapat didefinisikan sebagai sekumpulan masalah pencarian total yang dapat direduksi menjadi polytime menjadi END OF THE LINE :
END OF THE LINE : Sirkuit yang diberikan S dan P dengan n bit input dan n bit output sedemikian sehingga P (0 n ) = 0 n ! = S (0 n ) , cari input x dalam {0,1} n sedemikian rupa sehingga P (S (x)) ! = X atau S (P (x)) ! = X ! = 0 n .
Sirkuit atau algoritma seperti S dan P secara implisit mendefinisikan grafik besar secara eksponensial yang hanya terungkap berdasarkan permintaan-oleh-permintaan (untuk menjaga masalah di PSPACE !), Misalnya kertas Papadimitrou .
Namun, saya tidak mengerti bagaimana seseorang akan mendesain sebuah sirkuit yang memungkinkan grafik yang berubah-ubah (jika ada struktur sistematis pada grafik, tampaknya jauh lebih mudah untuk menemukan sirkuit). Sebagai contoh, bagaimana seseorang mendesain sirkuit berukuran polinomi yang merepresentasikan garis terarah secara eksponensial, dengan label semua-0 untuk simpul sumber dan label biner yang ditetapkan secara acak untuk semua simpul lainnya? Ini tampaknya tersirat dalam makalah terkait PPAD .
Yang paling dekat saya dari pencarian online adalah makalah Galperin / Widgerson , tetapi rangkaian yang dijelaskan di sana membutuhkan dua label titik dan mengembalikan jawaban Boolean untuk "Apakah simpul-simpul ini berdekatan?"
Jadi, bagaimana Anda mendesain rangkaian polinomially dari grafik berukuran eksponensial yang mengambil input n- bit dan mengeluarkan label n- bit dari pendahulunya atau penggantinya, masing-masing? Atau bahkan, apakah seseorang mengetahui sumber daya yang menjelaskan hal ini dengan baik?
sumber