Masalah yang diketahui terbuka dalam literatur dan masalah apa pun yang, setelah diajukan, diputuskan untuk dibuka oleh masyarakat.
Wikipedia hanya mencantumkan dua masalah di bawah "masalah yang tidak terpecahkan dalam ilmu komputer" : P = NP? Adanya fungsi satu arah Apa masalah besar lainnya yang harus ditambahkan ke daftar ini? Aturan: Hanya satu masalah per jawaban Berikan deskripsi singkat dan tautan apa pun yang...
Acak dua string dibentuk dengan memotong karakter ke string baru, menjaga karakter masing-masing string dalam urutan. Misalnya, MISSISSIPPIadalah shuffle dari MISIPPdan SSISI. Biarkan saya memanggil string kuadrat jika itu adalah shuffle dari dua string yang identik. Sebagai contoh, ABCABDCDadalah...
Latar Belakang Beberapa tahun yang lalu, ketika saya masih sarjana, kami diberi pekerjaan rumah tentang analisis diamortisasi. Saya tidak dapat menyelesaikan salah satu masalah. Saya telah menanyakannya dalam teori comp.the , tetapi tidak ada hasil yang memuaskan muncul. Saya ingat kursus TA...
Setelah mempelajari deterministic finite state automata (DFA) di tingkat sarjana, saya merasa mereka sangat dipahami. Pertanyaan saya adalah apakah ada sesuatu yang masih belum kita mengerti tentang mereka. Maksud saya bukan generalisasi DFA tetapi DFA asli yang tidak dimodifikasi yang kami...
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...
Pertimbangkan keluarga menguraikan himpunan bagian dari {1,2, ..., n}, F 1 , F 2 , ... F t .tttF1, F2, ... FtF1,F2,…Ft{\cal F}_1,{\cal F_2},\dots {\cal F_t} Seandainya (*) Untuk setiap dan setiap R ∈ F i , dan T ∈ F k , ada S ∈ F j yang berisi R ∩ T .saya < j < ki<j<ki \lt j \lt kR...
Pembaruan : Perangkat penghalang (yaitu "penghalang" NxM antara ukuran kotak yang dapat diwarnai dan yang tidak dapat diwarnai) untuk semua pewarnaan-empat-bebas-persegi monokromatik sekarang dikenal . Adakah yang mau mencoba 5 warna? ;) Pertanyaan berikut muncul dari Ramsey Theory...
Masalah ini terinspirasi oleh pertanyaan MO ini , yang menurut saya sangat menarik. Apa masalah terbuka tertua di TCS? Jelas pertanyaan ini membutuhkan klarifikasi. Pertama, apa itu TCS? Saya pikir keberadaan angka sempurna ganjil bukanlah TCS. Saya akan mengatakan bahwa masalah kesepuluh...
Baru-baru ini Gil Kalai dan Dick Lipton keduanya menulis artikel yang bagus tentang dugaan menarik yang diusulkan oleh Peter Sarnak, seorang ahli dalam teori bilangan dan Hipotesis Riemann. Dugaan. Biarkan menjadi fungsi Möbius . Misalkan adalah fungsi dengan input dalam bentuk representasi...
Masalahnya adalah menghitung polinomial . Asumsikan bahwa semua koefisien cocok dengan kata mesin, yaitu dapat dimanipulasi dalam satuan waktu.( a1x + b1) × ⋯ × ( anx + bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Anda dapat melakukan waktu dengan menerapkan FFT dalam...
Dalam semangat beberapa diskusi umum seperti ini , saya membuka utas ini dengan maksud untuk mengumpulkan pendapat tentang apa saja tantangan terbuka dan topik hangat dalam penelitian tentang bahasa pemrograman . Saya berharap bahwa diskusi ini bahkan dapat memunculkan pendapat tentang masa depan...
Saya ingin bertanya tentang kasus khusus dari pertanyaan " Memutuskan apakah sirkuit NC 0 yang diberikan menghitung permutasi " oleh QiCheng yang telah dibiarkan tidak terjawab. Sirkuit Boolean disebut sirkuit NC 0 k jika setiap gerbang keluaran secara sintaksis bergantung pada paling banyak...
Apakah masalah berikut NP-hard? Diberikan konfigurasi papan untuk draft internasional , temukan satu langkah hukum tunggal.n×nn×nn\times n Masalah terkait untuk catur Amerika (alias konsep bahasa Inggris) mudah dipecahkan dalam waktu polinomial. Ada tiga perbedaan utama antara kedua game...
Apakah algoritme waktu polinomial deterministik yang dikenal untuk masalah berikut: Input: angka alami nnn (dalam pengkodean biner) Output: bilangan prima p>np>np > n . (Menurut daftar masalah terbuka oleh Leonard Adleman, masalahnya terbuka pada 1995.)
Peringkat tanda dari matriks A dengan entri + 1, -1 adalah peringkat paling rendah (di atas real) dari matriks B yang memiliki pola tanda yang sama dengan A (yaitu, untuk semua i , j ). Gagasan ini penting dalam kompleksitas komunikasi dan teori belajar.SEBUAHsaya jBsaya j>
Untuk konstanta , seseorang dapat menentukan dalam waktu linier, diberikan grafik input , apakah treewidth -nya adalah . Namun, ketika dan diberikan sebagai input, masalahnya adalah NP-hard. ( Sumber ). Gk ∈ Nk∈Nk \in \mathbb{N}GGGk G≤ k≤k\leq kkkkGGG Namun, ketika grafik input adalah planar ,...
Pada tahun 1999, Petra Schuurman dan Gerhard J. Woeginger menerbitkan makalah "Algoritma perkiraan waktu polinomial untuk penjadwalan mesin: Sepuluh masalah terbuka" . Sejak itu, sejauh yang saya ketahui, ulasan yang menyangkut daftar masalah yang sama belum muncul. Dengan demikian akan sangat...
Misalkan kita diberi beberapa poligon sederhana terpisah di dalam pesawat, dan dua titik dan luar setiap poligon. Masalah jalur terpendek Euclidean adalah menghitung jalur terpendek Euclidean dari ke yang tidak memotong interior poligon apa pun. Untuk konkret, mari kita asumsikan bahwa koordinat...
Selain kompleksitas komunikasi (deterministik) dari suatu relasi , ukuran dasar lain untuk jumlah komunikasi yang dibutuhkan adalah nomor partisi protokol . Hubungan antara kedua ukuran ini diketahui hingga faktor konstan. Monograf oleh Kushilevitz dan Nisan (1997) memberikanRc c ( R )cc(R)cc(R)RRR...
Dalam makalah "A Compendium of Problem Complete for P" oleh Greenlaw, Hoover dan Ruzzo (PS) (PDF) , ada daftar masalah dalam P yang tidak diketahui berada di NC dan tidak diketahui juga P-complete. . (Daftar ini merangkum semua masalah terbuka dalam survei yang sangat baik oleh Karp dan...