Apakah PPAD benar-benar menangkap gagasan menemukan simpul yang tidak seimbang lainnya?

13

Kompleksitas kelas PPAD ditemukan oleh Christos Papadimitriou dalam makalah seminalnya tahun 1994 . Kelas dirancang untuk menangkap kerumitan masalah pencarian di mana keberadaan solusi dijamin oleh "Argumen paritas dalam grafik berarah": jika ada titik tidak seimbang dalam grafik berarah maka harus ada yang lain. Tetapi biasanya kelas secara formal didefinisikan dalam masalah ( ) masalah, di mana argumen hanya diterapkan pada grafik dengan baik di dalam dan outdegrees . Pertanyaan saya adalah: mengapa pengertian ini setara?ANOTHER END OF THE LINEAEOL1

Hingga saat ini, ini merupakan duplikat dari pertanyaan ini . Sekarang saya ingin menyatakan masalah secara formal dan menjelaskan mengapa saya tidak puas dengan jawaban di sana.

Masalah ( ): kami diberi dua sirkuit berukuran polinomial dan yang mendapatkan dan mengembalikan daftar polinomial dari elemen lain di . Sirkuit ini menentukan grafik berarah mana dan . Masalah pencarian adalah sebagai berikut: diberikan , dan sedemikian rupa sehingga , menemukan simpul lain dengan properti yang sama.ANOTHER UNBALANCED VERTEXAUVSPx{0,1}n{0,1}nG=(V,E)V={0,1}n(x,y)E(yS(x)xP(y))SPzVindegree(z)outdegree(z)

Masalah pencarian : sama, tetapi dan menghasilkan daftar kosong atau satu elemen.AEOLSP

Gagasan reducibilitas (dikoreksi sesuai dengan saran Ricky): masalah pencarian total dapat direduksi menjadi masalah pencarian total melalui fungsi polinom dan jika adalah solusi untuk dalam masalah berarti adalah solusi untuk di masalah . B f g y f ( x ) B g ( x , y ) x AABfgyf(x)Bg(x,y)xA

Pertanyaan formal : mengapa dapat direduksi menjadi ? Atau haruskah kita menggunakan gagasan reducibilitas lainnya?A E O LAUVAEOL

Christos Papadimitriou membuktikan teorema analog tentang PPA (Teorema 1, halaman 505) tetapi argumen tampaknya tidak bekerja untuk PPAD . Alasannya adalah bahwa simpul dengan keseimbangan derajat akan ditransformasikan menjadi simpul dengan keseimbangan derajat . Maka algoritma untuk dapat mengambil salah satu dari simpul ini dan mengembalikan yang lain. Ini tidak akan menghasilkan simpul baru untuk .k ± 1 A E O L A U V±kk±1AEOLAUV

Keadaan semakin memburuk karena dalam selalu ada jumlah genap yang tidak seimbang tetapi dalam mungkin ada jumlah ganjil dari mereka. Inilah sebabnya mengapa seseorang tidak dapat membangun sebuah bijih antara dua set ini dan tidak selalu sama dengan . Jika maka kita memperoleh metode untuk menyelesaikan dalam waktu polinomial setidaknya untuk beberapa contoh. Jika tidak bergantung pada dan untuk maka dapat dikembalikan sebagai jawaban untuk . Itu tidak akan memberikan solusi untukA U V g f - 1 g ( x , f ( x ) ) x A U V g x g ( y 1 ) = g ( y 2 ) y 1y 2 y 2 y 1 A U VAEOLAUVgf1g(x,f(x))xAUVgxg(y1)=g(y2)y1y2y2y1AUV .

Pertanyaan terakhir : dapatkah hambatan yang disebutkan di atas dapat diatasi? Bisakah seseorang menggunakan ketergantungan pada ?xgx

Daniil Musatov
sumber
2
"Mengapa pengertian ini setara?" Untuk alasan yang diberikan dalam bukti Teorema 1 di halaman 505 oleh Christos Papadimitriou. (Kalau tidak, menurut Anda apa argumen paritas untuk totalitas AUV?) Definisi Anda tentang reducibilitas tampaknya terlalu kuat - Misalnya, di bawah definisi Anda, memperluas rangkaian solusi dapat membuat masalah pencarian total menjadi lebih sulit.
2
+1 dan -1 memiliki paritas yang sama. (Paritas itu "aneh".)Yang benar memiliki "menyiratkan "bukan "IFF".g(x,y)g(y)
2
Sekarang, apa yang kita lakukan miliki adalah bahwa, saya akan menyebutnya UnbalancedInOtherDirectionVertex, bahwa masalah mengurangi ke PPADS , karena salah satu dapat flip tepi jika perlu untuk membuat diberikan vertex memiliki lebih keluar derajat dibandingkan derajat, dan kemudian Total -degree-1 vertex yang diberikan ditransformasikan menjadi semua akan menjadi sumber daripada tenggelam. Saya tidak melihat cara yang serupa untuk beralih dari masalah Anda ke AEOL. k
1
Setidaknya pengurangan menunjukkan bahwa AUV setara dengan kasusnya di mana semua simpul memiliki indegree dan outdegree paling banyak 1 kecuali mungkin untuk vertex z yang diberikan, yang memiliki indegree 0, tetapi mungkin memiliki outdegree besar.
Emil Jeřábek 3.0
2
Saya baru saja mendengar dari Frederic Meunier bahwa dia juga telah mengamati masalah ini lima tahun yang lalu dan Papadimitriou setuju.
domotorp

Jawaban:

4

Ini adalah pertanyaan yang menarik, dan saya hanya bisa memberikan jawaban parsial.

Sangat mudah untuk melihat bahwa konstruksi pada hal. 505 dari makalah Papadimitriou menunjukkan kesetaraan AUV dengan kasus khusus

BANYAK SELAMA LINE (MEOL): Diberikan grafik terarah dengan in-degree dan out-degree paling banyak 1 (diwakili oleh sirkuit seperti di atas), dan nonempty set X sumber G , temukan sink atau sumber v X .G1XGvX

Di satu sisi, saya merasa sulit membayangkan transformasi grafik yang dapat mengurangi jumlah sumber yang lebih besar menjadi satu.

Namun, di sisi lain, MEOL milik semua kelas yang dipelajari umumnya mengandung PPAD kecuali mungkin PPAD itu sendiri:

Pertama, jelas,

MEOL ada di PPADS .

Saya akan membuat sketsa di bawah argumen itu

MEOL dalam PPA

G=(V,E)X

|X|XX

s=|X|2k2sG=(V,E)2kVA,BV(A,B)EA={a0,,a2k1}B={b0,,b2k1}(ai,bi)Ei<2k

G1AVGAAX1

At=|AX|0<t2kt=2k=|A|AXp(a(s2k)p(ab)b+(ab)=apk, karena itu aneh. Selain itu, ada polinomial-waktu bijections antara , dan subset -element dari . Dengan ini, kita dapat mendefinisikan polinomial-waktu pencocokan pada semua kecuali satu dari subset -element dari . Kami menyertakannya dalam grafik, yang mengurangi jumlah sumber yang diketahui dengan menjadi .(s2k)[0,(ab))b[0,a)2kXt=2k1

Untuk , rumus penghitungan carry menunjukkan bahwa adalah genap. Sekali lagi, kita dapat menemukan yang cocok eksplisit pada subset -element dari . Kami memperluasnya ke sumber yang diketahui dengan dengan menerapkan pencocokan ke , dan membiarkan tetap.0<t<2k(st)tXA|AX|=tAXAX

Dengan cara ini, kami menghasilkan grafik tidak terarah dengan satu simpul daun yang dikenal. Kami meminta oracle PPA untuk daun lain, dan dengan konstruksi, kita dapat mengambil darinya jawaban untuk contoh MEOL .


Seperti yang disebutkan secara singkat oleh Papadimitriou, kita dapat menggeneralisasi PPA ke kelas PPA - untuk prima . Contoh masalah lengkap PPA - adalahppp

AUV - : Diberikan grafik berarah , dan sebuah simpul yang keseimbangan derajatnya , cari simpul lain yang serupa.GpG0(modp)

(Lihat jawaban ini untuk kesetaraan AUV - dengan definisi Papadimitriou tentang PPA - .)ppp

PPA - hanyalah PPA . Kelas PPA - diasumsikan berpasangan tak tertandingi, dan tak tertandingi dengan PPADS . Mereka semua termasuk PPAD .hal2p

Tidak ada yang khusus tentang dalam argumen yang saya uraikan di atas, dan dapat dengan mudah dimodifikasi untuk menghasilkanp=2

MEOL dalam PPA - untuk setiap prime .ppp

Emil Jeřábek 3.0
sumber
Saya sangat menyukai jawabannya dan telah memutuskan menerimanya (tentu saja, jawaban yang lebih lengkap masih disambut baik). Saya hanya berpikir bahwa kelas yang diwakili oleh AUV - harus disebut PPAD - . Papadimitriou menulis tentang grafik bipartit tidak berarah dan hanya derajat, bukan keseimbangan. ppp
Daniil Musatov
3
Kelas adalah generalisasi PPA, bukan PPAD, untuk . Papadimitriou memberikan masalah lengkap berbeda dari AUV- (catatan bahwa grafik nya adalah bipartit), tapi itu setara dengan definisi saya. Skema penamaan keseluruhan sangat membingungkan; penggunaan grafik terarah vs. tidak terarah untuk kelas tertentu hanya kebetulan, banyak kelas memiliki masalah lengkap tentang grafik terarah dan tidak terarah (seperti dalam kasus PPA- ). Juga, terlepas dari nama mereka, sebagian besar kelas tidak didasarkan pada argumen paritas, tetapi prinsip penghitungan lainnya. Hanya PPA tentang paritas. p pp=2pp
Emil Jeřábek 3.0
Terima kasih, mengerti. Memang kelas yang sama. Saya telah mendengar spekulasi bahwa Papadimitriou telah memilih nama PPAD karena menyerupai nama keluarganya sendiri.
Daniil Musatov
Apakah Anda memiliki referensi untuk PPAD berada di PPA-p?
domotorp
1
Bukan yang eksplisit, tetapi misalnya, masalah PPAD-complete yang mendefinisikan secara harfiah merupakan kasus khusus AUV- . p
Emil Jeřábek 3.0