Saya mencari contoh masalah dengan parametrized oleh angka k∈Nk∈Nk \in \mathbb{N} , di mana kekerasan masalahnya non-monotonik dalam kkk . Sebagian besar masalah (dalam pengalaman saya) memiliki transisi fase tunggal, misalnya kkk -SAT memiliki transisi fase tunggal dari k∈{1,2}k∈{1,2}k \in \{1,2\}...
Apakah Anda tahu algoritma masuk akal yang berjalan dalam waktu polinomial dalam (Panjang input + Panjang output), tetapi yang menjalankan waktu asimtotik dalam ukuran yang sama memiliki eksponen / konstanta yang sangat besar (setidaknya, di mana batas atas terbukti pada waktu berjalan adalah dalam...
Di utas Masalah utama yang belum terpecahkan dalam ilmu komputer teoritis? , Iddo Tzameret membuat komentar luar biasa berikut: Saya pikir kita harus membedakan antara masalah terbuka utama yang dipandang sebagai masalah mendasar, seperti , dan masalah terbuka utama yang akan menjadi terobosan...
Baru-baru ini, ketika berbicara dengan seorang ahli fisika, saya menyatakan bahwa dalam pengalaman saya, ketika masalah yang secara naif sepertinya membutuhkan waktu eksponensial ternyata secara nontrivial berada di P atau BPP, "alasan menyeluruh" mengapa pengurangan terjadi biasanya dapat...
Alat apa yang Anda gunakan untuk menulis makalah? Dari sedikit pengalaman yang saya miliki, para ahli teori menghabiskan banyak waktu untuk menulis dan memperbaiki makalah, selain benar-benar menjadi kreatif. Yaitu, mengomunikasikan pekerjaan mereka kepada orang lain. Mungkin makalah bukan cara...
Dua cara menganalisis efisiensi suatu algoritma adalah untuk menempatkan batas atas asimptotik pada runtime, dan untuk menjalankannya dan mengumpulkan data eksperimental. Saya ingin tahu apakah ada kasus yang diketahui di mana ada kesenjangan yang signifikan antara (1) dan (2). Maksud saya,...
Pertanyaan ini terinspirasi oleh pertanyaan lain tentang apa yang baru dalam PFDS sejak penerbitan buku Okasaki pada tahun 1998 . Saya akan mulai dengan dua pertanyaan yang saya miliki: Apakah ada struktur data set fungsional murni yang mendekati kecepatan tabel hash? Mencoba belum ada di...
Saya sering ditanya apa yang dilakukan ilmuwan komputer teoretis. Akan lebih baik memiliki beberapa tanggapan yang bagus untuk pertanyaan ini. Saya cenderung untuk kembali ke jargon teknis dan mata orang biasanya berkaca-kaca pada titik ini. Apa yang dilakukan ilmuwan komputer teoretis, dalam...
Mengikuti pertanyaan yang bermanfaat di MO , saya pikir akan bermanfaat untuk membahas beberapa nama kertas terkenal di CS. Cukup jelas bahwa kebanyakan dari kita mungkin tertarik untuk membaca (atau setidaknya melirik) sebuah makalah dengan judul yang menarik (setidaknya saya melakukannya setiap...
Secara informal, kompleksitas Kolmogorov dari string adalah panjang dari program terpendek yang menghasilkan x . Kita dapat mendefinisikan gagasan 'string acak' yang menggunakannya ( x adalah acak jika K ( x ) ≥ 0,99 | x | ) Mudah untuk melihat bahwa sebagian besar string adalah acak (tidak ada...
Hari ini Ryan Williams memposting artikel di arXiv (sebelumnya muncul di SIGACT News) berisi versi yang kurang teknis dari teknik batas bawah ACC baru-baru ini. Pertanyaan saya bukan tentang teknik itu sendiri (tentu saja layak pujian yang sangat besar), tetapi tentang gaya kertas. Dalam abstrak,...
Saat ini saya sedang menulis survei tentang teorema hierarki di TCS. Mencari makalah terkait saya perhatikan bahwa hierarki adalah konsep fundamendal tidak hanya dalam TCS dan matematika, tetapi dalam berbagai ilmu, dari teologi dan sosiologi ke biologi dan kimia. Melihat jumlah informasinya sangat...
Di MathOverflow, Timothy Gowers mengajukan pertanyaan berjudul " Mendemonstrasikan kekakuan itu penting ". Sebagian besar diskusi di sana tentang kasus-kasus yang menunjukkan pentingnya pembuktian, yang mungkin tidak perlu diyakinkan oleh orang-orang di CSTheory. Dalam pengalaman saya bukti perlu...
Apa saja aplikasi kode koreksi kesalahan dalam teori selain koreksi kesalahan itu sendiri? Saya mengetahui tiga aplikasi: Teorema Goldreich-Levin tentang bit inti keras, konstruksi ekstraktor Trevisan dan penguatan kekerasan fungsi boolean (oleh Sudan-Trevisan-Vadhan). Apa aplikasi 'serius' atau...
Tampaknya Teori Kompleksitas Geometrik membutuhkan banyak pengetahuan tentang matematika murni seperti geometri aljabar, teori representasi. Walaupun saya seorang siswa CS dan TIDAK memiliki kelas matematika yang sangat abstrak dan murni, saya tertarik dengan program ini. Apakah ada daftar...
Four Color Theorem (4CT) menyatakan bahwa setiap grafik planar adalah empat yang dapat diwarnai. Ada dua bukti yang diberikan oleh [Appel, Haken 1976] dan [Robertson, Sanders, Seymour, Thomas 1997]. Kedua bukti ini dibantu oleh komputer dan cukup menakutkan. Ada beberapa dugaan dalam teori grafik...
The jumlah kuadrat akar masalah bertanya, diberikan dua urutan dan b 1 , b 2 , ... , b n bilangan bulat positif, apakah jumlah Σ i √Sebuah1, a2, ... , ana1,a2,…,ana_1, a_2, \dots, a_nb1, b2, ... , bnb1,b2,…,bnb_1, b_2, \dots, b_n kurang dari, sama dengan, atau lebih besar dari...
Memutuskan apakah kesetimbangan Nash ada mudah (selalu terjadi); Namun, sebenarnya menemukan satu diyakini sulit (itu PPAD-Lengkap). Apa saja contoh masalah lain di mana versi keputusannya mudah tetapi versi pencariannya relatif sulit (dibandingkan dengan versi keputusan)? Saya akan sangat...
Bukti standar ikatan Chernoff (dari buku Acak Algoritma ) menggunakan Markov ketidaksetaraan dan fungsi menghasilkan momen, dengan sedikit ekspansi Taylor dilemparkan. Tidak ada yang terlalu sulit, tetapi agak mekanis. Tetapi ada bukti terikat Chernoff lainnya yang mengekspos struktur yang lebih...
Apa hasil paling mengejutkan dalam kompleksitas? Saya pikir akan bermanfaat jika memiliki daftar hasil yang tidak terduga / mengejutkan. Ini termasuk hasil yang mengejutkan dan muncul entah dari mana dan juga hasil yang ternyata berbeda dari yang diharapkan orang. Sunting : diberi daftar oleh...