Apakah masalah grafik isomorfisme telah terpecahkan?

13

Halaman masalah grafik isomorfisme Wikipedia tampaknya menunjukkan bahwa, tidak, itu belum diselesaikan. Namun, seorang teman saya menunjukkan Algoritma Waktu Polinomial untuk Grafik Isomorfisme . Saya tidak cukup canggih untuk mengikuti alasan di koran.

Saya memang memiliki usaha saya sendiri yang sangat kasar pada algoritma waktu polinomial tanpa sesuatu seperti bukti, tetapi saya ingin tahu apakah masalah ini telah berhasil diatasi sebelum melanjutkan.

Jadi, apakah masalah grafik isomorfisme terpecahkan?

complexity-theory reference-request time-complexity graph-isomorphism Tyler Spaeth
sumber
1
pertanyaan yang bermanfaat. Dengan peer review cyber, akan lebih baik jika responden / jawaban benar-benar menunjukkan kesalahan spesifik di koran daripada generalisasi. harus diakui peringatan di sini adalah apa yang para ilmuwan profesional pikirkan tentang jenis upaya ini. arxiv penuh dengan makalah yang keliru, banyak di P vs NP tetapi banyak masalah semifamous lainnya menarik upaya amatir, misalnya juga dugaan Collatz, prima kembar, dugaan Goldbach, dll.
vzn
7
@vzn Saya tidak berpikir ada gunanya membuang-buang waktu kita pada membaca makalah yang hampir pasti salah dan tidak memberi cahaya baru pada masalahnya.
Yuval Filmus
2
@vzn Saya tidak mengerti keluhan Anda. Jawaban DW (diposting satu jam sebelum komentar Anda) link ke komentar yang tidak titik keluar kesalahan tertentu di koran arXiv dalam pembahasan.
David Richerby
2
@vzn Kertas ArXiv berisi kesalahan. Itu belum direvisi untuk memperbaiki kesalahan itu. Tidak perlu lagi peer review. Saya tidak tahu apa yang Anda katakan adalah barang bekas: contoh tandingan adalah contoh tandingan, terlepas dari apakah itu disampaikan kepada Anda oleh penemunya atau oleh pengedar narkoba yang bergaul di belakang bar kumuh di Jalan tol.
David Richerby
1
@ vzn Agaknya, itu tidak direvisi karena penulis tidak dapat memperbaiki kesalahan. Perhatikan bahwa ArXiv tidak mengizinkan penarikan naskah, bahkan jika itu ternyata salah.
David Richerby

Jawaban:

23

Tidak. Makalah itu tampaknya cacat. Kelemahan ini dijelaskan dalam komentar oleh Tracy Hall on MathOverflow . Sebuah komentar tindak lanjut klaim bahwa penulis kemudian menyadari ada cacat dalam algoritma nya.

Seperti yang Yuval jelaskan, tidak jarang melihat upaya dari amatir untuk menyelesaikan masalah ini; mereka cenderung cacat. Ketika sampai pada hasil pada masalah terbuka yang terkenal (misalnya, P vs NP, grafik isomorfisme, dll.), Saya sarankan mencari literatur yang diterbitkan dalam konferensi dan jurnal peer-review terkemuka - peer review tidak sempurna, tetapi makalah peer-review memiliki kemungkinan yang jauh lebih tinggi untuk menjadi benar.

DW
sumber
17

Tidak, masalah grafik isomorfisme belum terpecahkan. Makalah yang Anda tautkan adalah dari 2007-2008, dan belum diterima oleh komunitas ilmiah yang lebih luas. (Kalau sudah, aku akan tahu tentang itu.)

Grafik isomorfisme, seperti banyak masalah terkenal lainnya, menarik banyak upaya oleh para amatir. Mereka hampir selalu salah. Saya akan menyarankan untuk tidak mencoba mengatasi masalah ini tanpa terlebih dahulu menjadi kompeten dalam matematika tingkat penelitian.

Yuval Filmus
sumber
2
cara lain untuk menangani jenis klaim oleh para ahli ini adalah ketidakmungkinan atau hasil penghalang. kemudian sanggahan yang lebih informatif berbentuk "makalah menggunakan tipe argumen [x] untuk mencoba menyelesaikan masalah isomorfisme, tetapi diketahui dari penelitian [a, b, c] bahwa ada penghalang khusus untuk tipe ini pendekatan, dan makalah ini tampaknya tidak menyadari penghalang ini atau mengungkapkan secara spesifik bagaimana itu diatasi. " ada hasil yang diketahui tentang ini untuk masalah isomorfisma & masalah utama lainnya misalnya P vs NP.
vzn
1
Mencoba masalah yang tidak terpecahkan seperti ini (dan gagal ..) dapat menjadi latihan pembelajaran yang sangat bermanfaat, jika seseorang datang dengan pola pikir yang benar.
Nick Alger
Namun, beberapa berdalih : bukti / klaim memiliki validitas untuk tingkat tertentu terlepas dari "penerimaan oleh komunitas ilmiah yang lebih luas" dan pengetahuan mereka oleh individu tertentu. misalnya ketika bukti yang benar pertama kali diperkenalkan, itu tidak langsung / instan "diterima" oleh orang lain selain penulis. dukungan lebih lanjut untuk dinamika ini dapat ditemukan dalam sejarah matematika. & Terkadang jangka waktu yang lama dapat terjadi antara pengenalan klaim / pernyataan dan penerimaan, misalnya dalam kasus Galois, Ramanujan dll
vzn
8

Saya akan sangat meragukan bahwa ia memiliki (dalam arti bukti keberadaan algoritma waktu polinomial). Meskipun bukan tidak mungkin kertas itu benar, ada sejumlah tanda peringatan:

  1. Penulis belum mempublikasikan hasilnya di tempat yang ditinjau oleh rekan sejawat (bahkan setelah 7 tahun).
  2. Penulis tampaknya tidak menerbitkan apa pun, di mana pun.
  3. Makalah ini menyajikan algoritma, tetapi klaim kebenaran adalah argumen handwaving informal tentang kompleksitas.
  4. Untuk masalah yang menentang upaya beberapa orang yang sangat pintar, perhitungan matematika di koran terlalu sederhana.
  5. Penulis tampaknya tidak berafiliasi dengan lembaga akademik. Versi baru makalah ini menjelaskan hal ini.

Sekali lagi, tanpa seseorang mengidentifikasi cacat di koran, ini bukan tanda bukti bodoh. Mungkin penulis memiliki kilasan wawasan yang unik dan kemudian beralih ke kehidupan yang sama sekali berbeda, tetapi bobot kemungkinan menentangnya - klaim luar biasa membutuhkan bukti luar biasa.

Untuk menguraikan (4) diberi berita baru-baru ini, László Babai baru-baru ini mengklaim peningkatan besar pada algoritma graph isomorphism yang diketahui (belum ada pracetak, tetapi komentar berjalan yang layak pada kuliah umum dapat ditemukan di sini ), memberikan algoritma waktu pseudo-polinomial. Babai dan rekan-rekannya adalah orang-orang yang sangat pintar, dan matematika yang digunakan untuk mendapatkan hasil ini sulit, dalam dan mencakup teori grafik dan teori grup. Mengingat bobot probabilitas, ini adalah level yang diharapkan untuk kemajuan signifikan pada masalah seperti ini.

Luke Mathieson
sumber
3
Poin 1-4 kuat tetapi 5 jauh lebih mendalam.
David Richerby
(5) salah institusi (tampaknya) adalah Universitas Teknik Berlin dan disponsori negara bagian. (1) didukung oleh perayap tautan / kertas ini. makalah ini dikutip di halaman klaim Woeginger .
vzn
3
Babai mencabut klaim runtime quasipolynomial . Ternyata ada kesalahan dalam analisis.
Raphael
klaim kuasipolinomial dipulihkan
miracle173
3

Laszlo Babai telah mengklaim telah menemukan solusi quasipolynomial untuk masalah grafik isomorfisme pada 11 November 2015.

... dan mencabut klaimnya kemarin (4/1/2017):

Sumber: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

bharv14
sumber
Dari tautan yang Anda berikan: Babai belum merilis pracetak, dan ketika saya bertanya kepadanya dia berkata "segera, segera." Sampai saat itu.
scaaahu
Pertanyaannya tidak mendefinisikan apa artinya masalah grafik isomorfisme dihitung sebagai dipecahkan, tetapi interpretasi yang paling mungkin adalah: bahwa seseorang telah menemukan algoritma waktu polinomial untuknya, atau memberikan bukti bahwa tidak ada algoritma waktu polinomial seperti itu. . Di bawah interpretasi itu, jawaban ini tidak menjawab pertanyaan.
DW
4
Babai mencabut klaim runtime quasipolynomial . Ternyata ada kesalahan dalam analisis.
Raphael
klaim kuasipolinomial dipulihkan
miracle173