Kolaborasi online besar-besaran untuk memecahkan masalah terbuka dalam ilmu komputer teoretis

Dalam proyek-proyek Polymath, sebuah kelompok besar mengerjakan masalah terbuka.

Masalah apa yang tampaknya paling berhasil dalam kerangka kerja ini?
Apakah ada kandidat yang baik untuk proyek polymath dalam ilmu komputer teoretis?
Adakah kendala yang membuat proyek Polymath lebih kecil kemungkinannya untuk berhasil dalam ilmu komputer teoretis dibandingkan dengan bidang matematika lainnya?

soft-question open-problem research-practice Joshua Herman
sumber

Polymath4 sudah fokus pada pertanyaan TCS: merancang algoritma deterministik yang lebih cepat untuk menemukan yang terbaik dalam rentang yang diberikan. Polymath3 berfokus pada dugaan Hirsch polinom, yang terkait erat dengan analisis algoritma simpleks. Maksud saya adalah, TCS adalah matematika, dan proyek polymath TCS tidak perlu berbeda dari proyek polymath lainnya.

Sasho Nikolov

ide yang hebat! tetapi tidak cocok dengan baik di stackexchange fmt. namun ruang obrolan dapat menjadi tempat alami / efektif untuk berorganisasi & telah digunakan untuk beberapa tujuan ini. telah ada beberapa pekerjaan kelompok TCS sesekali misalnya pada ulasan bukti deolalikar dll. tantangan utama dengan ilmu online / terbuka tampaknya menjadi insentif seperti yang diidentifikasi oleh Nielsen dalam bukunya yang sangat baik Networked science

vzn

Saya pikir proyek HoTT dengan blog yang didedikasikan, beberapa repositori GitHub, pertemuan tatap muka (dan pendirian publik) adalah model yang lebih menjanjikan untuk penelitian ilmu komputer teori kolaboratif daripada proyek Polymath "superstar math ajaib bertenaga".

Thomas Klimpel

@ThomasKlimpel Mengingat bahwa Hott berasal dari peraih medali Fields, dan bahwa buku Hott ditulis pada, dan dibiayai oleh IAS, sulit untuk melihat bagaimana Hott tidak juga "superstar math ajaib bertenaga".

Martin Berger

@ThomasKlimpel Saya minta maaf karena bersikap kasar tetapi saya pikir ini adalah komentar yang konyol. Untuk satu hal, Anda membandingkan upaya yang mengambil pendanaan besar dan pekerjaan organisasi non-sepele untuk model yang dapat diatur segera oleh siapa saja dan pada dasarnya memiliki biaya nol. Bagi yang lain, penolakan "keajaiban matematika superstar" tidak perlu dan salah arah. Gower, Tao, dan Kalai adalah ahli matematika ulung yang aktif online. Siapa lagi yang memimpin hal seperti itu? (Dan seperti yang ditunjukkan Martin, Voevodsky juga peraih medali Fields.)

Sasho Nikolov

Jawaban:

Proyek-proyek Polymath tampaknya berhasil ketika sebuah terobosan terjadi, dan seseorang mencoba untuk mengoptimalkan hasil dari terobosan tersebut atau menghasilkan bukti yang lebih sederhana atau lebih baik. Lihat https://en.wikipedia.org/wiki/Polymath_Project#Problems_solved . Karena itu, Anda harus memilih masalah seperti ini di CS. Satu-satunya yang langsung muncul di benak saya adalah meningkatkan konstanta dalam penggandaan matriks https://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efisien_matrix_multiplication , yang saat ini di 2.4 ... Tapi terus terang, saya tidak yakin orang cukup peduli dengan orang lain. cukup untuk mengerjakannya ...

Pertanyaan yang saya harapkan gagal secara menyedihkan: P = NP, optimalitas online, UGC, dll.

Sariel Har-Peled
sumber

Nah, beberapa waktu lalu, ada semacam proyek polymath untuk menganalisis bukti P = NP yang diumumkan, yang ternyata salah ...

J.-E.

Penggandaan matriks telah menjadi populer baru-baru ini ...

Yuval Filmus

Menemukan versi yang lebih bersih dari bukti teorema PCP mungkin merupakan upaya bermanfaat yang bisa mereka lakukan.

Phylliida

@ J.-E.Pin: jadi proyeknya sukses!

cody

rupanya Yuval terlalu sederhana untuk mengutip sendiri bekerja pada perkalian matriks. jika ada yang memposting komentar di posting itu (nol saat ini), itu bisa memulai kolaborsi dunia maya di sana. menunjukkan bahwa tantangannya bukanlah infrastruktur teknis sama sekali, yang telah ada di sana selama bertahun-tahun, tetapi (1) kurangnya tenaga ahli, dan (2) tenaga ahli di daerah menerapkan diri mereka dengan cara-cara lain yang khas / konvensional (misalnya menulis makalah, menghadiri konferensi dll)

vzn

Jika kolaborasi online yang besar telah diatur, maka ia harus mencoba untuk fokus pada masalah dengan peluang keberhasilan yang masuk akal. Tiga masalah konstruksi klasik zaman kuno dikenal sebagai "squaring the circle", "trisecting a angle", dan "doubling a cube". Matematika modern menyelesaikan ketiganya, tetapi jauh lebih penting adalah revolusi Descartes sebelumnya, yang memungkinkan matematika untuk membebaskan diri dari penjara mental kompas dan konstruksi straightedge. Perhatikan bahwa orang Yunani menggunakan kompas dan garis lurus sebagai perangkat komputasi yang praktis, seperti yang disaksikan oleh skema pendekatan epicycle yang efisien untuk perhitungan mekanika selestial.

Banyak dugaan dan generalisasi dugaan terselesaikan dari teori grafik harus dapat diterima untuk solusi melalui kolaborasi. Namun, pengalaman khas dengan kolaborasi menunjukkan bahwa tim yang terdiri dari 2-4 anggota jauh lebih efektif daripada tim yang jauh lebih besar. Contoh dari tim yang sangat sukses di bidang ini adalah N. Robertson, PD Seymour dan R. Thomas, yang menyerang masalah seperti dugaan grafik sempurna yang kuat, generalisasi dari empat teorema warna, dan grafik dugaan terkait kecil. Waktu yang berlalu antara pengumuman hasil baru dan publikasi mereka yang sebenarnya telah lama terkenal, juga untuk tim peneliti lain di bidang yang sama, menunjukkan bahwa volume kerja murni di sini memperlambat segalanya, sehingga kolaborasi (yang sudah terjadi) dapat bermanfaat untuk mempercepat. (SAYA'

Saat ini saya mencoba untuk memahami peran kelengkapan logika intuitionistic dalam aplikasi praktis dari sanggahan bukti berbantuan komputer. Tetapi jika Anda benar-benar berencana untuk melakukan pembuktian dengan kolaborasi besar-besaran secara online, maka memiliki sistem refutation proof berbantuan komputer yang solid mungkin benar-benar penting. Lagi pula, jika Anda tidak mengenal kolaborator Anda dengan cukup baik, bagaimana Anda bisa menilai apakah Anda dapat mempercayai kontribusi mereka, tanpa membuang banyak waktu untuk memeriksa semua yang mereka lakukan? (Saya memiliki kesan bahwa matematikawan lebih terbiasa untuk membuktikan penyangkalan dan menikmati sisi positifnya seperti umpan balik pribadi langsung, sementara para ilmuwan komputer menunjukkan kurang rutin dengan umpan balik semacam ini.)

Thomas Klimpel
sumber