Saya menanyakan pertanyaan ini 10 hari yang lalu di cs.stackexchange di sini tapi saya tidak punya jawaban. Dalam makalah yang sangat terkenal (di komunitas jaringan), Wang & Crowcroft menyajikan beberapa hasil perhitungan jalur di bawah beberapa kendala aditif / multiplikasi. Masalah pertama...
Atau dengan kata lain, apakah kita memiliki itu untuk setiap bahasa dan , atau ?SEBUAHSEBUAHABBBA ≤halBSEBUAH≤halBA \leq_p BB ≤halSEBUAHB≤halSEBUAHB \leq_p
Saya sedang mempelajari masalah yang sulit untuk kelas formula boolean yang dikuantifikasi dengan jumlah logaritmik dari pergantian quantifiers. Masalah di kelas ini akan terlihat seperti: ∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalogn−1,…xalogn)F∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalogn−1,…xalogn)F\forall...
Saya menemukan beberapa buku tentang komputer, tetapi semuanya tentang teknologi. Saya ingin sesuatu yang lebih terkait dengan
Dalam kursus pengantar saya untuk pemrograman, kita belajar tentang metode Inisialisasi-Pemeliharaan-Pemutusan untuk membuktikan suatu algoritma melakukan apa yang kita harapkan. Tapi kami hanya perlu membuktikan bahwa suatu algoritma yang sudah diketahui benar, benar. Kami tidak pernah diminta...
Kita semua tahu menunjukkan bahwa memiliki penghalang. Kita semua telah mempelajari hambatan ini karena kami percaya P ≠ N P .P≠ NPP≠NPP\ne NPP≠ NPP≠NPP\ne NP Namun anggap dan ada orang bijak yang percaya bahwa kemungkinan ada . Jika ini memang benar maka fakta bahwa kita belum melihat algoritma...
Saya memiliki polytope didefinisikan oleh .PPP{x:Ax≤b,x≥0}{x:Ax≤b,x≥0}\{ x : Ax \leq b, x \geq 0\} Pertanyaan: Diberikan simpul dari , apakah ada algoritma waktu polinomial untuk sampel seragam dari tetangga dalam grafik ? (Polinomial dalam dimensi, jumlah persamaan, dan representasi . Saya dapat...
Biarkan G menjadi pohon pada simpul 2n. The treewidth dari G, tw (G) = 1. Sekarang anggaplah kita menambahkan n edge ke G untuk mendapatkan grafik H. Batas atas yang mudah pada tw (H) adalah n + 1. Apakah ini pada dasarnya yang terbaik? Tampaknya entah bagaimana tw (H) harus O (sqrt (n)), tetapi...
Robin Milner mendefinisikan bigraphs sebagai jenis struktur grafis dengan struktur seperti grafik tetapi di mana node dapat bersarang. Mereka menggeneralisasi proses kalkulus seperti CCS dan ` kalkulus, tetapi Milner tampaknya bermaksud agar mereka digunakan secara lebih umum: seminar mencatat...
Pertimbangkan , di mana lambda_i> 0 dan Y_i didistribusikan sebagai standar normal. Batasan konsentrasi seperti apa yang dapat dibuktikan pada X, sebagai fungsi dari koefisien (tetap) lambda_i?X= ∑sayaλsayaY2sayaX=∑sayaλsayaYsaya2X = \sum_i \lambda_i Y_i^2 Jika semua lambda_i sama maka ini...
Jika Anda terbiasa dengan verifikasi program, Anda cenderung lebih suka membaca Pertanyaan sebelum Latar Belakang . Jika Anda tidak terbiasa dengan verifikasi program maka Anda mungkin masih dapat menjawab pertanyaan ini, tetapi Anda cenderung lebih suka membaca Latar Belakang terlebih...
Siapa yang memperkenalkan gagasan rekursi ? Dapatkah seseorang menjelaskan dari mana asalnya dan bagaimana pengaruhnya terhadap ilmu
Menanggapi pertanyaan lain, Ekstensi teori beta kalkulus lambda , Evgenij menawarkan jawabannya: beta + aturan {s = t | s dan t adalah istilah tertutup yang tidak dapat dipecahkan} di mana istilah M dipecahkan jika kita dapat menemukan urutan istilah seperti yang M aplikasi 's kepada mereka sama...
Teorema Rice menyatakan bahwa setiap properti nontrivial dari set yang dikenali oleh beberapa mesin Turing tidak dapat diputuskan. Saya mencari teorema tipe-Beras kompleksitas-yang memberi tahu kita sifat nontrivial dari set NP mana yang tidak bisa
Saya mahasiswa ilmu komputer sarjana dan saat ini saya sedang merencanakan proyek kelulusan saya. Saya perlu beberapa ide di bidang komputasi kuantum. ada
Dua makalah yang akan saya sertakan adalah: D. Kozen, "Pengindeksan kelas subkursif" , STOC, 1978. R. Ladner, "Tentang Struktur Pengurangan Waktu Polinomial" , JACM,
Ketika mencoba memperbaiki bug di perpustakaan, saya mencari makalah tentang menemukan subranges di pohon merah dan hitam tanpa hasil. Saya sedang mempertimbangkan solusi menggunakan ritsleting dan sesuatu yang mirip dengan operasi append yang biasa digunakan pada algoritma penghapusan untuk...
Masalah #SAT adalah masalah # -p diselesaikan kanonik. Ini masalah fungsi daripada masalah keputusan. Ia bertanya, diberi rumus boolean dalam logika proposisional, berapa banyak tugas memuaskan yang F miliki. Apa batas bawah terbaik di
Apakah ada cara untuk menyandikan turunan dari Jumlah Subset atau Masalah Partisi Angka sehingga solusi (kecil) untuk hubungan bilangan bulat menghasilkan jawaban? Jika tidak pasti, maka dalam arti probabilistik? Saya tahu bahwa LLL (dan mungkin PSLQ) telah digunakan dengan keberhasilan sedang...
Tujuan : Menyelesaikan dugaan bahwa tidak ada bidang proyeksi pesanan 12. Pada tahun 1989, menggunakan pencarian komputer pada sebuah Cray, Lam membuktikan bahwa tidak ada bidang proyektif pesanan 10 ada. Sekarang Angka Tuhan untuk Rubik's Cube telah ditentukan setelah hanya beberapa minggu...