Saya mencari referensi tentang `mengurangi 'pengurangan Turing ke banyak-satu pengurangan. Dalam benak saya ada pernyataan tentang bentuk berikut (pernyataan yang serupa juga akan memuaskan saya): Dalil. Jika , maka A ≤ 2 f m B t t .A≤fTBA≤TfB\mathsf{A}\leq_T^f \mathsf{B}A≤2fmBttA≤m2fBtt\mathsf...
Adakah yang berpikir tentang kemungkinan bahasa pemrograman, dan kompiler, sehingga kompiler dapat secara otomatis melakukan analisis asimptotik kasus terburuk? Kasus penggunaan yang ada dalam pikiran saya adalah bahasa pemrograman tempat saya menulis kode, dan kompilasi. Kompilator memberi tahu...
Baru-baru ini ada beberapa hasil baru pada studi eksperimental berbasis komputer dari Erdos Discrepancy Problem (EDP) (melalui solver SAT, dikutip di bawah). Masalah ini telah dikutip dan dipelajari oleh beberapa (T) peneliti CS. Namun (mungkin mendalam?) Tautan ke (T) CS tidak begitu jelas. Apa...
Masalah subgraph terhubung maksimum-berat adalah sebagai berikut: Input: grafik dan berat (mungkin negatif) untuk setiap titik .w i i ∈ VG=(V,E)G=(V,E)G=(V,E)wiwsayaw_ii∈Vsaya∈Vi \in V Keluaran: subset maksimum-berat dari simpul sedemikian sehingga terhubung.G [ S ]SSSG[S]G[S]G[S] Masalah...
Ada beberapa algoritme 2-aproksimasi untuk masalah set vertex umpan balik (FVS) TAK TERBATAS, yang dirangkum dalam [4]. Perhatikan bahwa pengurangan dari penutup simpul ke FVS adalah perkiraan-melestarikan. Dengan asumsi dugaan Game Unik, kami tidak dapat mengharapkan algoritma yang lebih baik....
Saya membacanya di sini bahwa ada keluarga fungsi yang memerlukan node pada jaringan saraf dengan paling banyak lapisan untuk mewakili fungsi sementara hanya perlu jika jaringan saraf memiliki setidaknya lapisan. Itu merujuk pada sebuah makalah oleh Hastad. Saya tidak menemukannya. Bisakah...
Untuk d⃗ ∈Nnd→∈Nn\vec{d} \in \mathbb{N}^n , misalkan Q(d⃗ )⊂NnQ(d→)⊂NnQ(\vec{d}) \subset \mathbb{N}^n adalah himpunan simpul dari kubus dimensi- nnn diskalakan ke arah koordinat ke- iii oleh didid_i , yaitu Q(d⃗ ={⟨±d1,…,±dn⟩}Q(d→={⟨±d1,…,±dn⟩}Q(\vec{d} = \{\langle \pm d_1, \ldots, \pm...
Grafik adalah bipartit lokal jika lingkungan terbuka dari setiap simpul menginduksi grafik bipartit. (Menurut penelusuran, nama yang sama dapat digunakan untuk hal lain yang terkait dengan permukaan). NP-hard untuk masalah grafik umum mana yang menjadi polinomial untuk grafik bipartit lokal dan...
Dalam film Inception Cobb meminta Ariadne untuk merancang labirin yang membutuhkan waktu dua kali lebih banyak untuk merancang. Ini cocok untuk masalah umum di mana kita memiliki situasi di mana kita terbatas sumber daya dengan jumlah tertentu dan siapa pun yang akan memverifikasi bahwa masalah...
Saya menemukan presentasi oleh Ryan O'Donnell tentang prinsip invarian. Setelah membuktikan teorema Berry-Esseen, ada slide yang membahas ekstensi teorema dan yang disebutkan ada apa yang disebut "versi derandomized ': Jika C -bagus (yaitu, telah membatasi momen ketiga), 3-bijaksana independen.,...
Adakah kompleksitas komunikasi acak yang diketahui (non-sepele) dengan batas bawah untuk masalah kesenjangan alami di mana 1-input secara linear jauh dari 0-input? Artinya, fungsi parsial sedemikian rupa sehingga jarak Hamming antara setiap ( x , y ) ∈ f - 1 ( 1 ) dan ( x ′ , y ′ ) ∈ f - 1 (f: { 0...
Saya sebelumnya menanyakan pertanyaan ini di Programmers.SE , tanpa hasil. Saya mencari sumber belajar tertulis tentang bagaimana merancang struktur data bersamaan. Saya lebih tertarik pada proses desain (misalnya, mengidentifikasi invarian yang tepat) daripada produk akhir (daftar kode...
Apa publikasi pertama dari konsep optimalisasi penggabungan berdasarkan mengidentifikasi urutan posisi berturut-turut dalam meningkatkan pesanan (alias berjalan) dalam waktu linier; kemudian berulang kali menggabungkan dua sekuens terpendek seperti itu dan menambahkan hasil penggabungan ini ke...
Salah satu hasil mendasar dalam kompleksitas parameter dari masalah grafik adalah bahwa COVER VERTEX di-parameterisasi oleh ukuran solusi adalah fixed-parameter-trable (FPT). Di sisi lain, ketika diparameterisasi oleh "parameter ganda" , itu menjadi setara dengan SET INDEPENDEN diparameterisasi...
Biarkan Alice dan Bob menghitung fungsi boolean .f(x1,…,x2n)f(x1,…,x2n)f(x_1,\dots,x_{2n}) Pilih subset acak dari kardinalitas n dan membiarkan J = { 1 , ... , 2 n } ∖ saya .I⊆{1,…,2n}I⊆{1,…,2n}\mathcal I\subseteq\{1,\dots,2n\}nnnJ={1,…,2n}∖IJ={1,…,2n}∖I\mathcal J=\{1,\dots,2n\}\backslash\mathcal...
Saya sudah lama bertanya-tanya tentang asal-usul nama "kebal" dan "sederhana". Saya juga mengajukan pertanyaan yang sama kepada Andrea Sorbi, yang pada gilirannya melibatkan beberapa rekan kerja lagi dalam diskusi. Tentang "sederhana" kami memiliki beberapa dugaan. Martin Davis mengemukakan bahwa...
Pertama, minta maaf jika pertanyaan ini sesuai atau sepele untuk situs ini. Saya seorang fisikawan yang mencari bantuan di luar zona nyamannya. Dalam PRL 87 167902 (2001) diklaim bahwa " ... untuk sewenang-wenang kecil terdapat kode error-correcting E : { 0 , 1 } n → { 0 , 1 } m dengan m ≤ n / δ...
The vertex jumlah isoperimetric dari grafik adalah . Beberapa makalah akademis menyatakan bahwa masalah penghitungan angka verteks isoperimetrik dari grafik adalah NP-hard, tanpa bukti atau referensi.G=(V,E)G=(V,E)G=(V,E) iV(G)=min{|N(S)||S|:S⊆V,1≤|S|≤|V|2}iV(G)=min{|N(S)||S|:S⊆V,1≤|S|≤|V|2}i_V(G)...
Apakah #P pertama kali diperkenalkan di [1] ? [1] Valiant, Leslie G. "Kompleksitas komputasi yang permanen." Ilmu komputer teoretis 8.2 (1979):
Pertimbangkan masalah set-persimpangan: Alice dan Bob masing-masing mendapatkan subset dari {1,…,n}{1,…,n}\left\{ 1,\ldots, n\right\} , dan mereka ingin tahu apakah set mereka berpotongan. Ini adalah masalah kanonik dari kompleksitas komunikasi, dan diketahui bahwa protokol acak untuk masalah ini...