Masalah menarik berikut muncul dalam penelitian saya baru-baru ini: INSTAN: Grafik .G ( V, E)G(V,E)G(V, E) SOLUSI: Selesai siklus aneh chordless, didefinisikan sebagai superset dari edge set sehingga grafik memiliki properti yang setiap tepi dalam terkandung dalam siklus aneh chordless. E G ′ ( V...
Saya baru saja membaca di Wikipedia bahasa Jerman bahwa grafik infinite adalah grafik dengan jumlah node yang tidak terbatas atau jumlah edge yang tidak terbatas. Saya hanya tahu aplikasi dan algoritma untuk grafik hingga. Apa gunanya grafik tak terbatas? Apa aplikasi itu? Saya tidak dapat...
Dua pertanyaan terkait tentang komputasi kedalaman terbatas: 1) Misalkan Anda mulai dengan n bit, dan untuk memulai dengan bit saya bisa 0 atau 1 dengan beberapa probabilitas p (i), secara independen. (Jika itu membuat masalah lebih sederhana, kita dapat mengasumsikan bahwa semua p (i) s adalah...
Grafik garis hypergraph adalah (sederhana) grafik memiliki tepi sebagai simpul dengan dua tepi berdekatan dalam jika mereka memiliki persimpangan nonempty. Hypergraph adalah -hypergraph jika masing-masing ujungnya memiliki paling banyak simpul.GHHHGGGHHHHHHGGGrrrrrr Apa kompleksitas masalah...
Sementara teorema Adleman menunjukkan, bahwa , saya tidak mengetahui adanya literatur yang menyelidiki kemungkinan dimasukkannya . Apa konsekuensi kompleksitas-teoretis yang akan dimiliki oleh inklusi seperti itu?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq
Biarkan menjadi kelas dari semua bahasa reguler.REGREG\mathsf{REG} Diketahui dan \ mathsf {REG} \ tidak \ subset \ mathsf {AC} ^ 0 . Tetapi apakah ada karakterisasi untuk bahasa di \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?AC0⊄REGAC0⊄REG\mathsf{AC}^0 \not\subset
Asumsikan kita ingin mengurutkan daftar dari bilangan real. Anggaplah kita diberi kotak hitam yang dapat mengurutkan bilangan real secara instan. Berapa banyak keuntungan yang bisa kita peroleh dengan menggunakan kotak hitam ini?n √SSSnnnn--√n\sqrt n Misalnya, dapatkah kita mengurutkan angka hanya...
Mengingat satu set keluarga himpunan bagian dari alam semesta . Biarkan dan kami ingin menjawab adalah .FF\mathcal{F}UUUS1,S2∈FS1,S2∈FS_1,S_2 \in \mathcal FS1⊆S2S1⊆S2S_1 \subseteq S_2 Saya mencari struktur data yang memungkinkan saya untuk dengan cepat menjawab ini. Aplikasi saya adalah dari teori...
Pertanyaan ini dimigrasikan dari Computer Science Stack Exchange karena dapat dijawab di Theoretical Computer Science Stack Exchange. Bermigrasi 6 tahun yang lalu . (Pertanyaan ini sedikit "survei".) Saya saat ini sedang mengerjakan masalah di mana saya mencoba untuk
Sudah diketahui bahwa palindrom dapat dikenali dalam waktu linier pada mesin Turing pita, tetapi tidak pada mesin Turing pita tunggal (dalam hal ini waktu yang dibutuhkan adalah kuadratik). Algoritma linear-waktu menggunakan salinan input, dan dengan demikian juga menggunakan ruang...
Cakar adalah . Algoritma trivial akan mendeteksi cakar dalam waktu . Ini dapat dilakukan dalam , di mana adalah eksponen dari perkalian matriks cepat, sebagai berikut: ambil subgraf yang diinduksi oleh untuk setiap simpul , dan temukan sebuah segitiga di komplemennya. O ( n 4 ) O ( n ω + 1 ) ω N [...
Diberikan reguler , apakah ada batasan non-sepele pada ukuran tata bahasa bebas konteks terkecil untuk ?R 1 ∩ ⋯ ∩ R nR1,…,RnR1,…,RnR_1, \dots, R_nR1∩⋯∩RnR1∩⋯∩RnR_1 \cap \cdots \cap
Seberapa cepat algoritma nondeterministic untuk menyelesaikan masalah EXPTIME harus menyiratkan P ≠ N PP≠NPP \neq NP ? Sebuah waktu polinomial algoritma nondeterministic akan segera menyiratkan ini karena P ≠ E X P T I M EP≠EXPTIMEP \neq EXPTIME tapi tidak ada yang percaya N P = E X P T I M...
Apakah ada kalkulus lambda yang diketik di mana logika yang sesuai di bawah korespondensi Curry-Howard konsisten, dan di mana ada ekspresi lambda yang diketik untuk setiap fungsi yang dapat dihitung? Ini memang pertanyaan yang tidak tepat, tidak memiliki definisi yang tepat tentang "kalkulus...
Saya punya dua pertanyaan historis: Siapa yang pertama kali menggambarkan perhitungan nondeterministik? Saya tahu bahwa Cook menjelaskan masalah NP-complete, dan bahwa Edmonds mengusulkan bahwa algoritma P adalah "efisien" atau "baik" algoritma. Aku mencari ini artikel Wikipedia dan skim "Di...
Katakanlah bahasa adalah P -density-close jika ada algoritma waktu polinomial yang memutuskan pada hampir semua input dengan benar.LLLLLLL Dengan kata lain, ada P , sehingga menghilang, yang berarti Ini juga berarti bahwa pada input acak yang seragam, algoritma polytime untuk A akan memberikan...
Wikipedia memberikan contoh masalah di mana versi penghitungannya sulit, sedangkan versi keputusannya mudah. Beberapa di antaranya menghitung kecocokan sempurna, menghitung jumlah solusi untuk -SAT dan jumlah penyortiran topologi.222 Apakah ada kelas penting lainnya (misalnya contoh dalam kisi,...
Tampaknya tidak ada gunanya penambangan cryptocurrency mengangkat pertanyaan tentang alternatif yang berguna, lihat pertanyaan ini tentang Bitcoin , CST , MO . Saya bertanya-tanya apakah ada algoritma yang dapat mengubah hampir semua tantangan komputasi (yang solusinya dapat diverifikasi secara...
Dilambangkan dengan wnwnw_n jumlah kata-kata panjang nnn dalam (mungkin ambigu) bahasa bebas konteks. Apa yang diketahui tentang wnwnw_n ? Saya yakin ini sudah banyak dipelajari, tetapi saya tidak dapat menemukan apa pun di
Ingat jumlah bilangan prima adalah fungsi penghitungan utama . Dengan "PRIMES dalam P", komputasi ada di #P. Apakah masalahnya # P-selesai? Atau, mungkin, ada alasan kerumitan untuk percaya bahwa masalah ini bukan # P-complete? π(n)π(n)\pi(n)≤n≤n\le nπ(n)π(n)\pi(n) PS Saya menyadari ini agak naif...