Sehubungan dengan Slither link puzzle, saya sudah bertanya-tanya: Misalkan bahwa saya memiliki grid sel persegi, dan saya ingin mencari siklus sederhana dari tepi kotak, seragam secara acak di antara semua siklus sederhana mungkin.n×nn×nn\times n Salah satu cara untuk melakukan ini adalah dengan...
Saya merumuskan masalah berikut hari ini saat bermain dengan GPS saya. Ini dia : Misalkan menjadi grafik berarah sehingga jika e = ( u , v ) ∈ E maka ( v , u ) ∉ E , yaitu, G adalah orientasi dari grafik tak berarah yang mendasarinya. Pertimbangkan operasi berikut:G ( V, E)G(V,E)G(V,E)e = ( u , v...
Saya sudah banyak membaca tentang sistem tipe dan semacamnya dan saya mengerti kira-kira mengapa mereka diperkenalkan (untuk menyelesaikan paradoks Russel). Saya juga memahami kira-kira relevansi praktis mereka dalam bahasa pemrograman dan sistem bukti. Namun, saya tidak sepenuhnya yakin bahwa...
Karena tidak ada tanggapan di Lambda the Ultimate, saya coba lagi di sini: istilah sistem penulisan ulang digunakan misalnya dalam teorema otomatis yang membuktikan perhitungan simbolis, dan tentu saja untuk mendefinisikan tata bahasa formal. Ada beberapa bahasa pemrograman yang berbasis pada...
Pertanyaan: Berapa ukuran rumus batas bawah paling dikenal untuk fungsi eksplisit di AC 0 ? Apakah ada fungsi eksplisit dengan batas bawah ?Ω(n2)Ω(n2)\Omega(n^2) Latar Belakang: Seperti kebanyakan batas bawah, ukuran rumus batas bawah sulit didapat. Saya tertarik pada rumus ukuran batas bawah...
Saya baru-baru ini membaca tentang parser Earley dan berpikir itu adalah salah satu algoritma paling elegan yang pernah saya lihat sampai saat ini. Namun, algoritma dalam pengertian tradisionalnya adalah sebuah pengenal dan bukan pengurai, yang berarti bahwa ia dapat mendeteksi apakah suatu string...
Pemecah SAT sangat penting dalam serangan aljabar , misalnya walksat dan minisat . Namun, ketika memecahkan masalah benchmark yang tersedia di sini ada perbedaan kinerja yang sangat besar antara keduanya - Walksat jauh lebih cepat daripada mini untuk masalah ini. Kenapa ini? Ini pelaksanaan...
Seperti yang disebutkan dalam judul, saya ingin tahu ada hubungan dan perbedaan antara CIC dan ITT. Bisakah seseorang menjelaskan atau menunjuk kepada saya beberapa literatur yang membandingkan kedua sistem ini? Terima
Hasil oleh Robertson dan Seymour menunjukkan sebuah algoritma untuk menguji apakah grafik tetap adalah minor dari . Saya punya dua setengah pertanyaan tentang topik ini:O(n3)O(n3)O(n^3)GGGHHH 1) Tampaknya telah ada peningkatan pada algoritma ini sejak. Apa algoritma paling terkenal saat ini? 2a)...
Saya telah membaca di beberapa makalah bahwa keberadaan fungsi satu arah diyakini secara luas. Adakah yang bisa menjelaskan mengapa ini terjadi? Argumen apa yang kita miliki untuk mendukung keberadaan fungsi satu
Saya akan menghadiri konferensi ilmu komputer pertama saya dan setelah membaca saran tentang cara meningkatkan konferensi, saya perhatikan beberapa saran tentang mahasiswa pascasarjana yang menghadiri konferensi pertama mereka. Apa nasihat yang Anda miliki untuk seorang mahasiswa pascasarjana yang...
Misalkan kita memiliki kelas objek (katakanlah grafik, string), dan relasi ekivalensi pada objek-objek ini. Untuk grafik ini bisa berupa grafik isomorfisme. Untuk string, kita bisa mendeklarasikan dua string yang setara jika mereka adalah anagram satu sama lain. Saya tertarik menghitung perwakilan...
Mengingat sebuah grafik diarahkan dan tertimbang dan integer bahkan , apa yang kompleksitas komputasi penghitungan set simpul sehingga dan subgraf dari terbatas himpunan titik mengakui pasangan yang cocok? Apakah kompleksitas # P-selesai? Apakah ada referensi untuk masalah ini?k S ⊆ V | S | = K G...
Pertanyaan ini muncul karena rasa ingin tahu yang murni (pertanyaan itu muncul sambil berpikir tentang melepaskan tali , tetapi saya tidak yakin apakah itu benar-benar terkait) jadi saya harap itu sesuai. Ada berbagai produk grafik, dan saya tertarik pada salah satu dari mereka di sini. Apa...
Volume III dari Knuth The Art of Computer Programming (pasal 5 ayat 3,2) termasuk mengikuti tabel daftar tepat jumlah minimum perbandingan yang diperlukan untuk memilih elemen th terkecil dari set disortir ukuran , untuk semua . Tabel ini, bersama dengan ekspresi bentuk tertutup terkenal dan ,...
Apa yang diketahui tentang kompleksitas masalah berikut: Diberikan: bilangan rasional .x1<x2<…<xnx1<x2<…<xnx_1 < x_2 < \dotso < x_n Output: bilangan bulat .y1≤y2≤…≤yny1≤y2≤…≤yny_1 \le y_2 \le \dotso \le y_n Tujuan: kecilkan mana∑1≤i<j≤ne(i,j),∑1≤i<j≤ne(i,j),\sum_{1 \le i <...
Szemeredi's Regularity Lemma mengatakan bahwa setiap grafik yang padat dapat diperkirakan sebagai penyatuan O ( 1)O(1)O(1) banyak grafik expander bipartit. Lebih tepatnya, ada partisi dari sebagian besar simpul ke dalam O ( 1 )O(1)O(1) set sehingga sebagian besar pasangan membentuk bipartit...
Baru-baru ini, Ryan Willams membuktikan bahwa Konstruktivitas dalam Bukti Alami tidak dapat dihindari untuk memperoleh pemisahan kelas kompleksitas: dan T C 0 . NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} Constructivity di Bukti Alam adalah suatu kondisi bahwa semua bukti kombinatorial di memenuhi...
Apa yang diketahui tentang kompleksitas komputasi bilangan bulat anjak di bidang bilangan umum? Lebih spesifik: Melalui bilangan bulat, kami mewakili bilangan bulat melalui ekspansi binernya. Apa representasi analog dari bilangan bulat di bidang bilangan umum? Apakah diketahui bahwa keutamaan...
Saya harap ini bukan pertanyaan politis yang salah untuk ditanyakan, tetapi untuk mahasiswa PhD yang biasanya menerbitkan di CCC / ITCS / ICALP (dan kadang-kadang di FOCS / STOC), mungkinkah berbahaya (karena karier) untuk menerbitkan karya yang kurang signifikan di konferensi yang kurang bergengsi...