Saya mencoba menemukan masalah yang kompleksitas ruang kasus rata-ratanya telah dianalisis. Lebih khusus, saya tertarik untuk mengetahui apakah ada masalah dengan kompleksitas ruang yang terbukti batas bawahnya yang super-linear, dan terutama jika ada dengan analisis kasus rata-rata (misalnya,...
Nurikabe adalah teka-teki isian kisi-kisi berbasis kendala, mirip dengan Minesweeper / Nonograms; angka ditempatkan pada kisi yang harus diisi dengan nilai on / off untuk setiap sel, dengan masing-masing angka menunjukkan wilayah terhubung 'on' sel dengan ukuran itu, dan beberapa kendala kecil pada...
Saya memiliki masalah yang ada di NEXP dan juga dapat diselesaikan dengan TM bergantian menggunakan waktu eksponensial dan hanya satu pergantian (mulai dalam keadaan eksistensial).NPNP^{\text{NP}} Adakah yang diketahui tentang NEXP ? Apakah setara dengan NEXP atau kelas lain? Apakah ada masalah...
Kelengkapan dan kesehatan dalam sistem bukti interaktif secara informal didefinisikan sebagai: Kelengkapan: Jika pernyataan itu benar, maka orang yang jujur dapat meyakinkan orang yang jujur akan kebenaran fakta ini . Keakuratan: Jika suatu pernyataan salah, pemalsu selingkuh tidak dapat...
Saya tidak ingat pernah melihat pemisahan kelas yang tidak didasarkan pada hasil diagonalisasi dan relatisasi. Diagonisasi masih dapat digunakan untuk memisahkan kelas yang diketahui yang tersisa, karena argumen non-relativiasi mungkin masih digunakan dalam kesimpulan diagonalisasi, atau dalam...
Jika , periode akan selalu menjadi pembagi . Jika Anda memilih dan untuk prime, maka kecuali Anda sangat beruntung, kami akan memiliki . Saya juga percaya bahwa kita dapat secara efisien menemukan bilangan prima dengan dengan memilih kandidat secara acak dan mengujinya (ini benar jika peristiwa...
Apa yang diketahui tentang transisi fase dalam masalah # P-Complete? Secara khusus, apakah ada transisi fase yang berbeda untuk # DNF-k-SAT dan # CNF-k-SAT? Pembaruan: Seperti yang kita ketahui, ada fase transisi dalam Random k-SAT di mana penyelesaian masalah berubah dari yang mudah ke sulit dan...
Bagaimana seseorang melihat suatu masalah dan alasan bahwa itu kemungkinan NP-Intermediate dibandingkan dengan NP-Complete? Seringkali cukup sederhana untuk melihat suatu masalah dan mengatakan apakah itu mungkin NP-Complete atau tidak, tetapi bagi saya tampaknya lebih sulit untuk mengatakan apakah...
Saya kira itu akan disebut # P-Space tetapi saya hanya menemukan satu artikel yang samar-samar menyebutkannya. Bagaimana dengan versi penghitungan masalah EXP-TIME-Complete, NEXP-Complete serta EXP-SPACE-Complete? Apakah ada karya sebelumnya yang dapat dikutip sehubungan dengan ini atau jenis...
Misalkan kita memiliki semigroup dengan elemen S = { s 1 , s 2 , ... , s n } . Tujuan kami adalah menghitung produk s i ∘ s i + 1 ∘ ⋯ ∘ s j .( S, ∘ )(S,∘)(S,\circ)S= { s1, s2, … , Sn}S={s1,s2,...,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracessaya∘ si + 1∘ ⋯ ∘ sjssaya∘ssaya+1∘⋯∘sjs_i\circ s_{i+1}\circ...
Dalam sistem kontrol versi terdistribusi (seperti Mercurial dan Git ) ada kebutuhan untuk secara efisien membandingkan grafik asiklik terarah (DAG). Saya adalah pengembang Mercurial, dan kami akan sangat tertarik untuk mendengar tentang karya teoretis yang membahas kompleksitas waktu dan jaringan...
Apakah ada masalah yang kompleksitas kasus rata-ratanya sama dengan kompleksitas kasus terburuknya? Apa sifat dasar dari masalah ini yang membuat mengurangi kasus terburuk menjadi
Saya tertarik pada variasi SAT di mana rumus CNF adalah monoton (tidak ada variabel yang dinegasikan). Formula seperti itu jelas memuaskan. Tetapi katakanlah jumlah variabel benar adalah ukuran seberapa baik solusi kami. Jadi kami memiliki masalah berikut: MINIMUM TRUE MONOTONE 3SAT INSTAN:...
Pertanyaan ini mungkin tidak bersifat teknis. Sebagai pembicara non-asli dan TA untuk kelas algoritma, saya selalu bertanya-tanya apa arti gadget dalam 'gadget klausa' atau 'gadget variabel'. Kamus mengatakan gadget adalah mesin atau perangkat, tapi saya tidak yakin apa artinya bahasa sehari-hari...
Saya bekerja di laboratorium ilmu saraf komputasi yang menghitung informasi timbal balik antara pasangan atau kelompok neuron. Baru-baru ini, bosnya menggeser fokusnya untuk mengukur "kompleksitas dinamika saraf". Dalam mengejar garis penelitian itu, beberapa orang dalam kelompok saya tampaknya...
Masalah 3-Clique Partition adalah masalah menentukan apakah simpul dari sebuah grafik, misalnya , dapat dipartisi menjadi 3 klik. Masalah ini NP-hard dengan pengurangan sederhana dari masalah 3-colorability. Tidak sulit untuk melihat bahwa jawaban untuk masalah ini mudah ketika diam ( G ) = 1 atau...
Dana Angluin ( 1987 ; pdf ) mendefinisikan model pembelajaran dengan pertanyaan keanggotaan dan pertanyaan teori (berlawanan dengan contoh fungsi yang diusulkan). Dia menunjukkan bahwa bahasa reguler yang diwakili oleh DFA minimal negara dapat dipelajari dalam waktu polinomial (di mana fungsi yang...
Teorema produk langsung, secara informal, mengatakan bahwa komputasi contoh fungsi f lebih sulit daripada komputasi f satu kali.kkkffffff Teorema produk langsung khas (misalnya, XOR Lemma Yao) melihat kompleksitas kasus rata-rata , dan berdebat (sangat kasar) bahwa tidak dapat dihitung oleh...
Itu ditunjukkan dalam makalah "Program Integer dengan Jumlah Variabel Tetap" bahwa program integer dengan jumlah konstan kendala (atau variabel) dapat dipecahkan secara polinomi. Apakah ini berlaku untuk pemrograman
Jawab: tidak dikenal Terima kasih banyak untuk semua yang membantu memperbaiki pertanyaan ini dan definisi yang terkait dengannya. Definisi wiki ini memberikan titik awal untuk wiki TCS yang lebih baru " Apakah P berisi bahasa yang keberadaannya tidak bergantung pada PA atau ZFC? (Wiki komunitas...