Dapatkah grafik isomorfisme diputuskan dengan nondeterminisme dibatasi oleh akar kuadrat?

Nondeterminism dibatasi mengaitkan fungsi dengan kelas bahasa diterima oleh mesin Turing deterministik sumber daya dibatasi, untuk membentuk kelas baru - . Kelas ini terdiri dari bahasa-bahasa yang diterima oleh beberapa mesin Turing nondeterministic mematuhi batas sumber daya yang sama seperti yang digunakan untuk mendefinisikan , tetapi di mana diizinkan untuk membuat paling banyak bergerak nondeterministic. (Saya menggunakan notasi Goldsmith, Levy dan Mundhenk, bukan yang asli oleh Kintala dan Fischer, dan $g(n)$ $C$ $g$ $C$ $M$ $C$ $M$ $g(n)$ $n$ adalah ukuran input.)

Pertanyaan saya:

Apakah ada yang konstan sehingga GRAFIK isomorfisma dalam $c\ge0$ -? $c\sqrt{n}$ $\mathsf{PTIME}$

( Sunting: Joshua Grochow menunjukkan bahwa jawaban positif untuk pertanyaan ini akan menyiratkan algoritma untuk GI yang memiliki batas runtime asimptotik yang lebih baik daripada yang diketahui saat ini. Karena itu saya akan dengan senang hati mengendurkan ikatan, memungkinkan gerakan nondeterministic.) $o(\sqrt{n}\log n)$

Latar Belakang

Untuk setiap konstanta tetap , - , karena gerakan nondeterministic menghasilkan paling banyak jumlah polinomial konfigurasi untuk dieksplorasi secara deterministik. Selain itu , dan dengan cara melapisi seseorang dapat menunjukkan bahasa NP-lengkap dalam - untuk setiap $c \ge 0$ $\mathsf{PTIME} = {c\log n}$ $\mathsf{PTIME}$ $c\log n$ $\mathsf{NP} = \cup_c n^c\text{-}\mathsf{PTIME}$ $n^\varepsilon$ $\mathsf{P}$ . $\varepsilon > 0$

Kintala dan Fischer mengamati bahwa memutuskan apakah grafik input dengan simpul memiliki -clique adalah -complete, tetapi dalam $V$ $(|V|/3)$ $\mathsf{NP}$ -. Untuk melihat ini, buang simpul yang memiliki paling banyaktetangga. Jika ada terlalu sedikit simpul yang tersisa, maka tolak. Kalau tidak, simpul yang tersisa membentuk grafik ukuran. Lalu tebak-subset simpul menggunakan $O(\sqrt{n})$ $\mathsf{PTIME}$ $|V|/3 - 2$ $\Omega(|V|^2)$ $|V|/3$ langkah-langkah nondeterministik dan memverifikasi bahwa mereka membentuk klik dalam waktu polinomial. $|V| = O(\sqrt{n})$

Beberapa bahasa lain dari grafik padat dalam juga dalam $L$ $\mathsf{NP}$ -. Ini adalah kasus untuk setiap masalah di mana subset dari simpul berfungsi sebagai sertifikat, dan ukuran grafik input adalah. Contohnya adalah versi janji dari Induced Path atau 3-Coloring untuk kasus grafik padat. Masalah lain tampaknya memerlukan sertifikat lebih besar, misalnya daftar simpul mendefinisikan sirkuit Hamilton tampaknya memerlukan $O(\sqrt{n})$ $\mathsf{PTIME}$ $\Omega(|V|^2)$ $\Omega(|V| \log |V|)$ bit. Tidak jelas bagi saya apakah seseorang dapat menggunakan jumlah nondeterminisme yang terlalu kecil untuk menebak sertifikat untuk memutuskan masalah seperti itu.

Mengingat bahwa - dapat berisi bahasa NP-complete, maka tampaknya menarik untuk bertanya di mana dalam hierarki nondeterminisme terbatas berpotensi bahasa lebih mudah jatuh. Orang mungkin mengharapkan GI, sebagai bahasa yang tampaknya tidak menjadi NP-lengkap, berada di hirarki lebih dekat dengan - daripada - . Namun, sertifikat yang jelas untuk GI menentukan peta menggunakan bit, yaitu $n^\varepsilon$ $\mathsf{P}$ $\log n$ $\mathsf{P}$ $n$ $\mathsf{P}$ $|V|\log |V|$ . $\omega(\sqrt{n})$

Cara lain untuk memikirkan pertanyaan ini: adalah menentukan peta antara set simpul sertifikat yang sesingkat mungkin untuk GI?

Sunting: Beberapa komentar lebih lanjut (dikoreksi) mengikuti, untuk menanggapi komentar Joshua Grochow.

Jika sertifikat menggunakan bit dan dapat diperiksa dalam waktu polinomial, maka brute force memberikan algoritma untuk pengambilan GI waktu. Dengan sertifikat ukuran $f(n) = \Omega(\log n)$ $poly(n)2^{O(f(n))} = 2^{O(f(n))}$ , brute force memberikan algoritma pengambilan $O(\sqrt{n})$ waktu, sementara sertifikat ukuran $2^{O(\sqrt{n})}$ menghasilkan pendekatan brute force dengan mengambil $O(\sqrt{n}\log n)$ waktu. Batas atas Luks lama adalah $2^{O(\sqrt{n}\log n)}$ waktu, yang berada di antara kedua batas ini hingga eksponen konstan. $2^{O(\sqrt{n\log n})}$

Pertimbangan ini menunjukkan bahwa mungkin ada pendekatan alternatif untuk GI. Pendekatan Luks tampaknya bergantung pada intinya pada mengidentifikasi subset generator dari kelompok terkait. Oleh karena itu mesin nondeterministic mungkin menebak subset dari grup. Himpunan bagian ini kemudian dapat diperiksa secara mendalam untuk menghasilkan algoritma deterministik. Jika daftar elemen dapat ditentukan secara ringkas, baik karena grup terkait tidak pernah lebih besar dari ukuran grafik, atau karena jumlah generator yang dibutuhkan selalu kecil, dan memeriksa setiap subset kandidat tidak memakan waktu terlalu lama, maka ini mungkin menghasilkan pendekatan alternatif untuk GI.

Chandra MR Kintala dan Patrick C. Fischer, Penyempurnaan Nondeterminisme dalam Relativized-Polynomial-Time Bounded Computation , SIAM Journal on Computing 9 (1), 46–53, 1980. doi: 10.1137 / 0209003
Judy Goldsmith, Matius A. Levy, Martin Mundhenk, Nondeterminisme terbatas , SIGACT News 27 (2), 20-29, 1996. doi: 10.1145 / 235767.235769
László Babai dan Eugene M. Luks, Labeling Grafis Kanonik , STOC 1983, 171–183. doi: 10.1145 / 800061.808746

cc.complexity-theory graph-theory graph-isomorphism nondeterminism András Salamon
sumber

Jadi, jika grafik diberikan sebagai matriks adjacency ukuran

apakah itu berarti saya dapat membuat jumlah linier dari gerakan non-deterministik wrt ke vertex set size

n^{2}

$n^2$

n

$n$

John D.

@ user17410: Ya, representasi seharusnya tidak terlalu penting, asalkan ukuran dari instance apa pun adalah

. (Jika bantalannya tidak masuk akal memiliki ukuran

maka tentu saja batasan akar kuadrat sudah cukup.)

O (| V |^{2})

$O(|V|^2)$

Ω ((| V | \log | V |)^{2})

$\Omega((|V|\log|V|)^2)$

András Salamon

Saya pikir Anda mungkin meminta algoritma yang lebih baik daripada yang paling dikenal ... Jika saya mengerti, sebuah

Algoritma

akan menghasilkan

O (\sqrt{n}) - P T I M E

$O(\sqrt{n})-\mathsf{PTIME}$

algoritma deterministik. Algoritma deterministik yang paling dikenal saat ini membutuhkan waktu

2^{O (\sqrt{n})}

$2^{O(\sqrt{n})}$

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

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

Joshua Grochow

@ AndrásSalamon: Brute force =

BUKAN

n! p o l y (n) \approx 2^{O (n \log n)}

$n!poly(n) \approx 2^{O(n \log n)}$

... Juga, saya tidak melihat mengapa sertifikat ukuran

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

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

mengarah ke algoritma brute force waktu

\sqrt{n}

$\sqrt{n}$

daripada

2^{\sqrt{n} \log n}

$2^{\sqrt{n} \log n}$

- dapatkah Anda menjelaskan? Mungkin saya kehilangan sesuatu dalam definisi notasi "PTIME"?

2^{O (\sqrt{n})}

$2^{O(\sqrt{n})}$

Joshua Grochow

@ MohammadAl-Turkistany: Mungkin, tapi saya harus memikirkannya sedikit. Ada beberapa poin dalam algoritma Babai di mana, begitu derajat warna berada di bawah polylog, ia menerapkan tes GI deg-deged, seperti pada algoritma terbaik sebelumnya, dan tidak jelas apakah seseorang dapat membuat tes GI polylog deg menjadi polylog-bounded nondeterminisme, atau apakah seseorang dapat melanjutkan rekursi Babai lebih jauh untuk mendapatkan derajat ke, katakanlah, derajat warna konstan. Jika dan ketika saya memikirkannya, saya akan memperbarui jawaban saya - jika Anda memiliki pemikiran tentang hal ini, saya senang mengobrol, tetapi ini mungkin bukan tempat yang tepat untuk mengerjakannya.

Joshua Grochow

Pertama, (seperti yang sekarang telah diedit ke pernyataan pertanyaan) jawaban positif untuk pertanyaan Anda akan segera meningkatkan keadaan seni dalam batas kasus terburuk untuk grafik isomorfisme. Untuk Algoritmamenghasilkan $O(\sqrt{n})-\mathsf{PTIME}$ algoritma deterministik waktu, tetapi saat ini yang paling dikenal untuk GI hanya $2^{O(\sqrt{n})}$ $2^{O(\sqrt{n \log n})}$

Kedua, bahkan tidak segera jelas bagi saya apakah algoritma terbaik saat ini sebenarnya adalah algoritma, meskipun bagian pertama dari itu jelas, dalam arti tertentu. Algoritme pertama-tama menebak seperangkat simpul ukuran $O(\sqrt{n \log n})-\mathsf{PTIME}$ untuk individual (Trik Zemlyachenko - lihat disiniuntuk penjelasan dalam Bahasa Inggris), yang dapat dilakukan dengan menebak $\sqrt{n/\log n}$ bit tidak ditentukan. Namun, setelah menebak mereka dan individualistis (dalam waktu poli deterministik), itu berlaku yang dibatasi derajat tes isomorfisma paling terkenal, yang membutuhkan waktu (Teorema 9.1 daritulisan ini), dan menerapkannya dalam kasus $\sqrt{n \log n}$ $n^{O(d /\log d)}$ . Saya harus berpikir dengan hati-hati tentang apakah algoritma yang terakhir dapat diubah menjadi $d=O(\sqrt{n \log n})$ Algoritma(sepertinya pertanyaan yang menarik ...) $O(\sqrt{n \log n})-\mathsf{PTIME}$

Joshua Grochow
sumber

Apakah Anda memiliki tautan ke versi yang tidak berada di belakang paywall? Saya belum pernah melihat implementasi sebenarnya dari trik Zemlyachenko atau tes derajat isomorfisme yang dibatasi. Memisahkan simpul dengan derajat seperti NAUTY mempercepat, tetapi mereka dengan derajat yang sama Anda masih harus memeriksa semua permutasi siklus prima pada mereka AFIK.

Chad Brewbaker

@Chad: Sayangnya saya tidak mengetahui versi non-paywalled dari artikel tersebut. Namun, trik Zemlyachenko cukup sederhana untuk diterapkan dalam praktik dan pada dasarnya mengurangi derajatnya. Untuk implementasi praktis trik Zemlyachenko, saya pikir satu-satunya pertanyaan adalah pertukaran antara enumerasi set verteks untuk individual (ukuran eksponensial dalam set) dan setiap potensi keuntungan yang dibuat dengan mengurangi derajat secara efektif. Saya tidak tahu apakah ini benar-benar diimplementasikan dalam NAUTY atau algoritma isomorfisme praktis lainnya.

Joshua Grochow

G

$G$

π

$\pi$

π (G)

$\pi(G)$

G

$G$

π

$\pi$

G

$G$

π (G)

$\pi(G)$

n

$n$

n!

$n!$

Dapatkah grafik isomorfisme diputuskan dengan nondeterminisme dibatasi oleh akar kuadrat?

Latar Belakang

Jawaban: