Konsekuensi dari algoritma waktu kuasi-polinomial untuk masalah grafik isomorfisme

Masalah Graph Isomorphism (GI) bisa dibilang kandidat yang paling dikenal untuk masalah NP-intermediate . Algoritma yang paling dikenal adalah algoritma sub-eksponensial dengan run-time . Diketahui bahwa GI bukan-complete kecualihierarki polinomialnyaruntuh. $2^{O(\sqrt{n \log n})}$ $\mathsf{NP}$

Apa yang akan menjadi konsekuensi teoretis kompleksitas dari algoritma waktu kuasi polinomial untuk masalah Graph Isomorphism?
Apakah algoritma waktu kuasi-polinomial untuk GI membantah dugaan terkenal dalam teori kompleksitas?

Masalah serupa lainnya seperti Minimum Dominating Set in Tournaments problem, Group Isomorphism, dan Tournament Isomorphism memiliki algoritma quasi-polynomial time ( QP ). Dua masalah selanjutnya adalah polinomial-waktu yang dapat direduksi menjadi GI.

Bisakah kita secara efisien mengurangi masalah Minimum Mendominasi Set di Turnamen menjadi GI?
Apakah ada dugaan yang mengesampingkan GI yang sulit untuk QP?

Pembaruan (2015-12-14) : Babai telah memposting makalah pendahuluan di arXiv untuk algoritme kuasipolinomial-waktunya untuk GI.

Pembaruan (2017-01-04) : Babai menarik kembali klaim bahwa algoritme tersebut dalam waktu kuasipolinomial, menurut analisis baru, algoritme tersebut dalam waktu subeksponensial yang ada di dalam . $\exp \exp(\tilde{O}(\sqrt{\lg n}))$ $2^{n^{o(1)}}$

Pembaruan (2017-01-09) : Babai mengembalikan klaim waktu semasipolinomial, menggantikan prosedur yang menyinggung dengan yang lebih efisien.

cc.complexity-theory ds.algorithms graph-theory graph-isomorphism Mohammad Al-Turkistany
sumber

Saya pikir banyak orang berpikir itu memiliki algoritma waktu polinomial, dan AFAIK algoritma semacam itu tidak akan memiliki konsekuensi teoritis kompleksitas.

Huck Bennett

Ini bukan yang Anda minta, tapi itu yang terbaik yang saya tahu: Group Isomorphism memiliki algoritma waktu-polinomial waktu semu dan polinomial yang mudah, tetapi tidak ada pengurangan

dari GI menjadi GroupIso: eccc. hpi-web.de/report/2010/117 . Pertanyaan yang secara formal lebih mudah daripada yang Anda tanyakan, tetapi masih terbuka lebar, adalah untuk membuktikan bahwa tidak ada pengurangan waktu-poli dari GI ke GroupIso.

{A C}^{0}

$\mathsf{AC}^0$

Joshua Grochow

Setelah dua tahun saya yakin kami punya jawaban. Laszlo Babai telah membuktikan bahwa GI memiliki algoritma waktu polinomial semu. Sumber: lucatrevisan.wordpress.com/2015/11/03/...

user3415207

@ user3415207 Babai mencabut klaim runtime quasipolynomial . Ternyata ada kesalahan dalam analisis.

Raphael

@Raphael ... dan Babai memulihkan klaimnya (tautan yang sama dengan milik Anda).

Danny

Jawaban:

Sejauh yang saya tahu, jika Anda bertanya tentang konsekuensi dari fakta (sebagai kotak hitam) bahwa GI ada di QP, saya pikir jawabannya sangat sedikit. Satu hal yang dapat saya pikirkan, yang bukan teorema tetapi konsekuensi untuk arah penelitian, adalah untuk Kelompok Isomorfisme. Karena GroupIso berkurang menjadi GI dan kami bahkan tidak tahu apakah GroupIso ada di P, menempatkan GroupIso ke dalam P dapat dilihat sebagai hambatan penting untuk memasukkan GI ke dalam P (jika Anda berpikir yang terakhir adalah masalahnya).

Namun, karena algoritma sepele untuk GroupIso adalah , kembali ketika kompleksitas GI naik pada $n^{\log n + O(1)}$ , kami memiliki jalan panjang dalam meningkatkan kompleksitas GI sebelum GroupIso menjadihambatan yangrelevanuntuk menempatkan GI menjadi P. Tetapi jika GI berada di QP, maka GroupIso menjadi hambatan yang jauh lebih relevan untuk perbaikan lebih lanjut dalam GI. (Tentu saja, eksponen eksponen dalam kuasi-polinomial masih berpotensi celah yang relevan, tetapi kesenjangan menjadijauhlebih kecil ketika GI berada di QP.) $2^{\tilde O(\sqrt{n})}$

Joshua Grochow
sumber

Tampaknya kita tidak dapat meningkatkan pada batas atas yang jauh lebih lemah dari pengujian isomorfisme dari pesawat projektif (

). Lihat cstheory.stackexchange.com/questions/34773/…

n^{O (\log \log n)}

$n^{O(\log \log n)}$

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Ya, tapi kemudian argumen saya yang sama berlaku: jika GI "naik" di quasipoly, maka ProjPlaneIso sangat jauh dari halangan untuk menempatkan GI ke dalam P. Begitu GI ada dalam waktu

untuk beberapa

, maka ProjPlaneIso akan menjadi hambatan yang relevan. Jadi, pada saat ini, tampaknya GroupIso adalah hambatan yang lebih langsung - mungkin suatu hari nanti ProjPlaneIso akan menjadi ...

n^{O (\log \log n)^{c}}

$n^{O(\log \log n)^c}$

c

$c$

Joshua Grochow

@JoshuaGrochow Apakah Anda setuju dengan saya bahwa pendekatan yang diambil oleh François Le Gall dan David J. Rosenbaum dalam On the Group and Color Isomorphism Problem masuk akal? Atau setidaknya mereka memperlakukan beberapa pertanyaan yang bisa muncul setelah mendapatkan pemahaman dasar tentang hasil László Babai?

Thomas Klimpel

@ThomasKlimpel: Saya setuju bahwa makalah mereka masuk akal, meskipun saya belum melihat bagaimana memanfaatkan wawasan mereka (meskipun memahami sebagian besar bukti Babai).

Joshua Grochow

β_{k} P

$\beta_k P$

$\varnothing$ $\Sigma^*$

Emil Jeřábek mendukung Monica
sumber

Apa yang akan menjadi konsekuensi teoretis kompleksitas dari algoritma waktu kuasi polinomial untuk masalah Graph Isomorphism?

Kurang lebih mirip dengan konsekuensi dari algoritma waktu polinomial deterministik untuk pengujian primality, algoritma waktu polinomial deterministik untuk pemrograman linier, dan kasus lain di mana algoritma (acak) yang praktis efisien (dengan contoh patologis langka di mana algoritma menjadi tidak efisien) diketahui. dan digunakan untuk waktu yang lama. Ini mengkonfirmasi dugaan bahwa efisiensi praktis adalah indikator yang baik untuk keberadaan algoritma teoritik deterministik mengatasi masalah contoh patologis yang langka.

Apakah algoritma waktu kuasi-polinomial untuk GI membantah dugaan terkenal dalam teori kompleksitas?

Tidak, dugaan tersebut lebih mengarah ke situs yang berlawanan, yaitu bahwa GI ada di P. Karena GI ada di NP, maka tidak akan mungkin untuk menyangkal dugaan jenis ini dalam waktu dekat.

Bisakah kita secara efisien mengurangi masalah Minimum Mendominasi Set di Turnamen menjadi GI?

Minimum Dominating Set bukan merupakan masalah isomorfisme, oleh karena itu tidak ada alasan mengapa hal itu diharapkan dapat direduksi menjadi GI.

Apakah ada dugaan yang mengesampingkan GI yang sulit untuk QP?

Kami bahkan tidak tahu bagaimana mengurangi masalah string isomorfisma menjadi GI, dan ini setidaknya masalah isomorfisme. Bukti Babai menunjukkan bahwa string isomorfisme ada di QP, jadi ... Dan apa yang sulit bagi QP artinya? Sulit di bawah pengurangan waktu polinomial?

Dari pengantar Masalah Kelompok dan Warna Isomorfisme oleh François Le Gall dan David J. Rosenbaum

Kompleksitas masalah pengujian isomorfisme layak dipelajari baik karena mereka adalah pertanyaan komputasi mendasar dan juga karena banyak dari mereka tidak diketahui berada di P, tetapi tetap tampak lebih mudah daripada masalah NP-complete. Yang paling banyak dipelajari adalah masalah isomorfisme grafik.

$\mathsf{GI}^*$ $\mathsf{GrI}^*$ didefinisikan (dalam makalah di atas, tetapi penulis benar bertanya-tanya mengapa tidak ada yang melakukannya sebelumnya), yang menambahkan potongan-potongan yang hilang dari masalah string isomorphism. (Dan masalah isomorfisma warna hanyalah nama yang berbeda untuk masalah string isomorfisme. Masalah automorfisme warna nama kembali ke makalah awal Babai dan Luks, nama string isomorfisma muncul kemudian dalam makalah mereka pada pelabelan kanonik.)

$\mathsf{GI}^*$

Sunting: Jawaban ini diberikan dalam konteks pencabutan hasil Babai, sebelum ia mengumumkan perbaikan. Ini menunjukkan bahwa sedikit generalisasi dari grafik masalah isomorfisma yang disarankan oleh masalah string isomorfisme adalah masalah yang sangat penting. Harapan tersirat di sini adalah bahwa algoritma yang masuk akal untuk masalah isomorfisme grafik akan mengarah pada algoritma yang sama untuk masalah isomorfisme grafik umum. Masalah umum adalah waktu polinomial setara dengan masalah set-stabilizer , masalah persimpangan grup , masalah persimpangan coset, masalah transporter set , ... Gagasan di balik harapan ini adalah bahwa masalah umum akan terjadi di bagian rekursifdari algoritma yang masuk akal, jadi harus tetap ditangani. (Dan sangat mungkin masalah yang digeneralisasikan adalah waktu polinomial yang setara dengan grafik isomorfisme.)

Sekarang komentar Joshua Grochow menunjukkan bahwa saya tidak berhasil menjelaskan pentingnya konseptual bagian yang hilang dari masalah string isomorphism. Untuk struktur tanpa batas, mungkin lebih mudah untuk menghargai bahwa isomorfisme yang valid tidak hanya mempertahankan struktur yang diberikan, tetapi juga termasuk dalam kategori fungsi yang sesuai (misalnya kategori fungsi kontinu). Untuk struktur terbatas, fenomena analog sebagian besar terjadi untuk struktur hasil bagi, di mana kategori fungsi yang sesuai harus kompatibel dengan quotients yang diberikan. Barang-barang Johnson adalah contoh khas dari quotients tersebut, misalnya logika partisi bekerja pada dua himpunan bagian elemen dari beberapa set dasar. Juga perhatikan bahwa membatasi kategori yang diperbolehkan untuk isomorfisma sering membuat masalah pengujian isomorfisme lebih mudah,

Masalah dengan generalisasi grafik masalah isomorfisme adalah di mana harus berhenti. Mengapa tidak menggeneralisasi sejauh yang mencakup masalah isomorfisma kelompok permutasi? Pertanyaan ini sangat sulit, karena banyak hasil non-sepele untuk graf isomorfisma mungkin akan terbawa ke isomorfisma kelompok permutasi juga. Tapi di sini rasanya lebih masuk akal untuk memperlakukan teori kelompok permutasi komputasi sebagai subjek dalam dirinya sendiri, bahkan jika memang memiliki hubungan dekat dengan masalah grafik isomorfisme.

Thomas Klimpel
sumber

$S_n$

@JoshuaGrochow Untuk iso warna, warnanya hanya angka acak (wlog terbatas pada [n]). Untuk string iso, string diberikan lebih dari alfabet terbatas tetap. Saya pikir itu adalah alfabet biner, tetapi saya salah mengingat ini. Saya hanya ingat bahwa saya awalnya bingung apakah warna iso hanya nama yang berbeda untuk string iso. Jadi ketika saya memutuskan untuk membaca koran itu setelah Laszlo mencabut klaimnya, rasanya seperti perbedaan bagi saya. Mungkin itu benar-benar perbedaan, karena "lebih dari alfabet terbatas" berkomunikasi "memperbaiki alfabet terbatas favorit Anda, itu tidak akan membuat perbedaan". Yang mana yang benar.

Thomas Klimpel

\log n

$\log n$

[n]

$[n]$

@JoshuaGrochow Inilah yang saya maksudkan dengan itu tidak akan membuat perbedaan ". Yang benar. Saya sekarang mencoba untuk mengatasi" String isomorphism / color isomorphism tidak termasuk dalam kelas itu "komentar. Saya senang belajar beberapa pelajaran dari Andreas Blass dan Yuri Gurevich di jalan, yang juga mencoba untuk fokus pada poin konseptual.Saya senang Babai memperbaiki algoritme-nya sekarang, sehingga saya tidak merasa berkewajiban (atau tekanan) untuk menyelidiki apakah grafik isomorfisme dan string isomorfisma adalah waktu polinomial setara (Yang merupakan konteks mengapa saya menulis jawaban itu.)

Thomas Klimpel

Saya bingung mengapa Anda membandingkan kemajuan GI dengan hasil derandomisasi.

Sasho Nikolov