Pertanyaan yang diberi tag open-problem

Masalah yang diketahui terbuka dalam literatur dan masalah apa pun yang, setelah diajukan, diputuskan untuk dibuka oleh masyarakat.

117
Seberapa keras unshuffling string?

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...

58
Buka masalah di perbatasan TCS

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...

37
Kisi-

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...