Saya ingin tahu apakah ketidakseragaman membantu fungsi komputasi dalam praktik. Mudah untuk menunjukkan bahwa ada fungsi dalam , mengambil fungsi yang tidak dapat dihitung dan mempertimbangkan bahasa { }, yang jelas memiliki sirkuit sederhana yang tidak seragam , tetapi tidak dapat dihitung secara...
Ini mungkin pertanyaan dasar, tapi saya sudah membaca dan mencoba memahami makalah tentang mata pelajaran seperti perhitungan ekuilibrium Nash dan pengujian degenerasi linier dan tidak yakin bagaimana bilangan real ditentukan sebagai input. Misalnya, ketika dinyatakan bahwa LDT memiliki batas...
Saya baru saja mengajarkan algoritma mincut acak Karger-Stein di kelas algoritma lulusan saya. Ini adalah permata algoritmik yang nyata , jadi saya tidak bisa mengajarinya, tetapi selalu membuat saya frustrasi, karena saya tidak tahu aplikasi lain dari teknik utama. (Jadi sulit untuk menetapkan...
Jika adalah diarahkan grafik -regular dan adalah bagian dari simpul-simpul kardinalitas , sebut ekspansi tepi dari kuantitasG=(V,E)G=(V,E)G=(V,E)dddSSS≤|V|/2≤|V|/2\leq |V|/2SSS ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|} Dimana...
Peter Shor menunjukkan bahwa dua masalah NP-intermediate yang paling penting, anjak piutang dan masalah log diskrit, ada di BQP. Sebaliknya, algoritma kuantum yang paling dikenal untuk SAT (pencarian Grover) hanya menghasilkan peningkatan kuadratik daripada algoritma klasik, mengisyaratkan bahwa...
Apa itu "daerah mudah" untuk kepuasan? Dengan kata lain, kondisi yang cukup untuk beberapa pemecah SAT untuk dapat menemukan tugas yang memuaskan, dengan asumsi itu ada. Salah satu contoh adalah ketika masing-masing klausa berbagi variabel dengan beberapa klausa lain, karena bukti LLL yang...
Saya sudah memikirkan masalah berikut untuk sementara waktu, dan saya belum menemukan solusi polinomial untuk itu. Hanya sumber kasar. Saya sudah mencoba untuk mengurangi masalah NP-Complete ke dalamnya juga tanpa keberhasilan. Inilah masalahnya : Anda memiliki set yang diurutkan...
Saya minta maaf jika pertanyaan ini agak kabur, tetapi saya ingin tahu bagaimana para peneliti yang sukses mendapatkan "perasaan" untuk hasil di TCS. Misalnya, aljabar linier dapat dipahami secara geometris, atau dalam hal interpretasi fisiknya (vektor eigen dapat dianggap sebagai "titik stabil"...
Hal ini diketahui bahwa diberi nnn bagian-titik dari ℓd2ℓ2d\ell_2^d (yang, diberikan nnn poin di RdRd{\mathbb R}^d dengan jarak Euclidean) adalah mungkin untuk menanamkan mereka isometrically di .ℓ(n2)1ℓ1(n2)\ell^{n\choose 2}_1 Apakah isometri dapat dihitung pada waktu polinomial (mungkin,...
Saya mencari kode koreksi kesalahan dari jenis berikut: kode biner dengan laju konstan, didekodekan dari beberapa fraksi konstan kesalahan, oleh decoder diimplementasikan sebagai sirkuit Boolean ukuran , di mana N adalah panjang pengkodean.O(N)O(N)O(N)NNN Beberapa latar belakang: Spielman,...
Saya mengalami sedikit kesulitan untuk sepenuhnya memahami langkah-langkah terakhir dari algoritma anjak piutang Shor. Diberikan ingin kita faktor, kita memilih acak yang memiliki urutan .x rNNNxxxrrr Langkah pertama melibatkan pengaturan register dan menerapkan operator Hadamard. Langkah kedua...
Saya adalah seorang ilmuwan komputer yang mengambil kursus tentang Topologi (taburan topologi set-point yang penuh dengan teori kontinum). Saya menjadi tertarik pada masalah keputusan yang menguji deskripsi ruang (secara sederhana) untuk properti topologi; yang dipertahankan hingga...
Yang mengejutkan saya, saya tidak dapat menemukan makalah tentang ini - mungkin mencari kata kunci yang salah. Jadi, kita punya array apa saja, dan fungsi pada indeksnya; adalah permutasi.fffffff Bagaimana kita menyusun ulang susunan menurut fff dengan memori dan runtime sedekat mungkin dengan O...
Saya belum berhasil menemukan struktur data ini, tetapi saya bukan ahli di bidang ini. Struktur mengimplementasikan himpunan, dan pada dasarnya adalah array elemen yang sebanding dengan invarian. Yang invarian adalah sebagai berikut (didefinisikan secara rekursif): Array dengan panjang 1 adalah...
Secara umum dianggap tidak mungkin bahwa komputer kuantum akan dapat menyelesaikan masalah NP-complete secara efisien. Dalam kasus klasik, salah satu pendekatan untuk mengatasi masalah tersebut adalah dengan menggunakan algoritma aproksimasi. Apakah ada penelitian tentang algoritma aproksimasi...
Saya tertarik pada contoh masalah di mana teorema yang tampaknya tidak ada hubungannya dengan mekanika kuantum / informasi (misalnya menyatakan sesuatu tentang benda-benda klasik murni) tetap dapat dibuktikan menggunakan alat kuantum. Sebuah survei Bukti Kuantum untuk Teorema Klasik (A. Drucker, R....
Apa kerumitan memutuskan apakah rangkaian dengan bit input dan bit output menghitung permutasi dari ? dengan kata lain, apakah setiap string bit di merupakan output dari rangkaian untuk beberapa input? Sepertinya masalah yang telah dipelajari, tetapi saya tidak dapat menemukan
Mengapa bahasa reguler (dan dari ekspresi reguler itu) disebut "reguler"? Ada banyak keteraturan juga dalam bahasa bebas konteks dari jenis bahasa lainnya. Saya menduga bahwa, pada awalnya, kata sifat "biasa" telah digunakan untuk membedakan jenis bahasa itu dari bahasa "non-reguler" atau entah...
Saya menjadi bingung oleh perbedaan halus antara proposisi dan penilaian ketika terkena teori tipe intuitionistic. Bisakah seseorang menjelaskan kepada saya apa gunanya membedakan mereka dan apa yang membedakan mereka? Terutama mengingat Curry-Howard
Saat membaca artikel "Apakah Saatnya Menyatakan Kemenangan dalam Menghitung Kompleksitas?" di blog "Surat Hilang Godel dan P = NP" , mereka menyebutkan dikotomi untuk CSP. Setelah beberapa link berikut, googling dan wikipeding, saya menemukan Teorema Ladner : Teorema Ladner: Jika , maka ada...