Jika kita melihat teorema hierarki DTIME, kita punya log karena overhead dalam simulasi Mesin Turing deterministik oleh mesin universal: D TsayaM.E( flogf) ⊊ D TsayaM.E( f)DTsayaM.E(flogf)⊊DTsayaM.E(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) Kami belum memiliki overhead semacam ini untuk...
1980-an memunculkan model komputasi paralel paralel PRAM dan BSP . Tampaknya masa kejayaan kedua model adalah selama akhir 80-an dan awal 90-an. Apakah area ini masih aktif dalam hal penelitian untuk algoritma paralel? Apakah ada model yang lebih baru dan lebih canggih untuk komputasi paralel?...
Apakah seseorang berani mencoba untuk menjelaskan apa hubungan bidang studi ini atau bahkan mungkin memberikan jawaban yang lebih konkret di tingkat masalah? Seperti yang termasuk yang mengasumsikan beberapa formulasi diterima secara luas. Jika saya mendapatkan ini dengan benar, ketika Anda beralih...
Richard J. Lipton telah terpilih sebagai pemenang Hadiah Knuth 2014 "untuk Pengenalan Gagasan dan Teknik Baru". Menurut Anda, apa ide dan teknik baru utama yang dikembangkan Lipton? Catatan. Pertanyaan ini akan menjadi wiki komunitas, harap cantumkan satu ide, teknik, atau hasil per...
Saya ingin mencari algoritma waktu polinomial yang menentukan apakah rentang set matriks yang diberikan berisi matriks permutasi. Jika ada yang tahu jika masalah ini dari kelas kompleksitas yang berbeda, itu akan sangat membantu. EDIT: Saya telah menandai pertanyaan ini dengan Linear...
Apa konsekuensi buruk NP = PSPACE? Saya terkejut saya tidak menemukan apa-apa tentang ini, mengingat bahwa kelas-kelas ini adalah yang paling terkenal. Secara khusus, apakah akan ada konsekuensi pada kelas
Sepertinya ini tidak diketahui - tetapi apakah ada batas bawah yang menarik pada kompleksitas perkalian matriks dalam model komputasi kuantum? Apakah kita memiliki intuisi yang dapat mengalahkan kompleksitas algoritma Coppersmith-Winograd menggunakan komputer
Diketahui bahwa jalan acak dalam kisi dua dimensi akan kembali ke asal dengan probabilitas 1. Juga diketahui bahwa jalan acak yang sama dalam TIGA dimensi memiliki probabilitas kurang dari 1 untuk kembali ke asal . Pertanyaanku adalah: Apakah ada sesuatu di antara keduanya? Sebagai contoh,...
Apakah bahasa { } bebas konteks atau tidak?aibjck | i≠j,i≠k,j≠kaibjck | i≠j,i≠k,j≠ka^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k Saya menyadari bahwa saya telah menemukan hampir semua varian pertanyaan ini dengan kondisi yang berbeda tentang hubungan antara i, j, dan k, tetapi tidak yang...
Saya mengajar kursus algoritma tingkat lanjut dan ingin memasukkan beberapa topik yang berkaitan dengan pembelajaran mesin yang akan menarik bagi siswa saya. Sebagai hasilnya, saya ingin mendengar pendapat orang tentang hasil algoritmik yang paling menarik / terbesar saat ini dalam pembelajaran...
Sudah diketahui bahwa ekspresi reguler dapat dikenali oleh otomat terbatas nondeterministik dengan ukuran yang sebanding dengan ekspresi reguler, atau oleh FA deterministik yang berpotensi lebih besar secara eksponensial. Lebih lanjut, diberikan string sss dan ekspresi reguler rrr , NFA dapat...
Untuk masalah aliran maksimum , tampaknya ada sejumlah algoritma yang sangat canggih, dengan setidaknya satu dikembangkan baru-baru ini tahun lalu. Max Orlin mengalir dalam waktu O (mn) atau lebih baik memberikan algoritma yang berjalan dalam O (VE). Di sisi lain, algoritma yang paling sering saya...
Tetapkan i oioio - S U B E X PSUBEXPSUBEXP untuk menjadi kelas bahasa LLL sedemikian rupa sehingga ada bahasa dan untuk tak terhingga banyaknya , dan menyetujui semua contoh panjang . (Yaitu, ini adalah kelas bahasa yang dapat "dipecahkan secara tak terhingga, dalam waktu subeksponensial".)L ′ ∈ ∩...
Mengutip Wikipedia , "[Permainan Kehidupan Conway] memiliki kekuatan mesin Turing universal: yaitu, apa pun yang dapat dihitung secara algoritmik dapat dihitung dalam Permainan Kehidupan Conway." Apakah hasil seperti itu meluas ke versi berisik dari Conway's Game of Life? Versi paling sederhana...
Dalam beberapa pertanyaan terakhir ( q1 q2 ), telah ada diskusi tentang "Teori A" vs "Teori B", yang tampaknya menangkap kesenjangan antara studi logika dan bahasa pemrograman dan studi tentang algoritma dan kompleksitas. Terminologi ini baru bagi saya, dan pencarian web cepat tidak menghasilkan...
Setiap bilangan alami dapat dianggap sebagai urutan bit, jadi memasukkan bilangan alami sama dengan memasukkan urutan 0-1, sehingga masalah NP-lengkap dengan input alami jelas ada. Tetapi apakah ada masalah alami, yaitu masalah yang tidak menggunakan beberapa pengkodean dan interpretasi khusus dari...
Dalam satu kalimat: apakah akan ada hierarki untuk menyiratkan hasil derandomisasi?BPTIMEBPTIME\mathsf{BPTIME} Pertanyaan yang terkait tetapi tidak jelas adalah: apakah keberadaan hierarki untuk menyiratkan adanya batas bawah yang sulit? Apakah resolusi masalah ini menabrak penghalang yang dikenal...
Diketahui bahwa dengan seperangkat algoritma yang dapat dihitung (dicirikan oleh nomor Gödel), kita tidak dapat menghitung (membangun algoritma biner yang memeriksa kepemilikan) semua himpunan bagian dari N. Sebuah bukti dapat diringkas sebagai: jika kita bisa, maka himpunan semua himpunan bagian...
Baru-baru ini, seorang teman saya (bekerja di TCS) menyebutkan dalam sebuah percakapan bahwa "dia ingin melihat / mengetahui semua (atau sebanyak mungkin) hasil indah di TCS dalam hidupnya". Jenis ini membuat saya bertanya-tanya tentang hasil yang indah di bidang ini dan karenanya motivasi untuk...
Ini adalah pertanyaan lanjutan untuk Apa perbedaan antara bukti dan program (atau antara proposisi dan tipe)? Program apa yang sesuai dengan bukti non-konstruktif (klasik) dari bentuk ∀k T(e,k)∨¬∀k T(e,k)∀k T(e,k)∨¬∀k T(e,k)\forall k \ T(e,k) \lor \lnot \forall k \ T(e,k) ? (Asumsikan bahwa TTT...