Untuk kompleksitas Kolmogorov diinduksi oleh bahasa deskripsi dasarnya-optimal, apakah ada bilangan bulat c sehingga untuk semua bilangan bulat positif n , ada string x sedemikian rupa sehinggaKK\hspace{.02 in}Kcccnnnxxxn<K( x )<n+cn<K(x)<n+c\;\;\; n \: < \: K(x) \: < \:...
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...
Biarkan menjadi masalah grafik NP-complete. Misalkan X dapat dipecahkan dalam waktu polinomial pada grafik dengan diameter terikat. Dengan kata lain, X yang diparameterisasi dengan diameter ada di XP. (Ingat masalah ada di XP jika bisa diselesaikan dalam waktu n f ( k ) ). Apakah ini menyiratkan...
vv_v[v]={0,1,…,v−1}[v]={0,1,…,v−1}[v] = \{0,1,\dots,v-1\}kkkkkkkkkvv_vs ∞ = lim k → ∞ s ksk=infM{δ∣∃c∀v(M decides k-SATv in 2vδ−c) time)}sk=infM{δ∣∃c∀v(M decides k-SATv in 2vδ−c) time)}s_k = \inf_M\{\delta \mid \exists c\forall v\;( M\text{ decides } k\text{-SAT$_v$ in }2^{v\delta-c})\text{ time})...
\newcommand{\cc}[1]{\mathsf{#1}} Apakah teorema di sepanjang baris berikut ini berlaku: Jika g(n)g(n)g(n) sedikit lebih besar dari f(n)f(n)f(n) , maka NTIME(g)∩coNTIME(g)≠NTIME(f)∩coNTIME(f)NTIME(g)∩coNTIME(g)≠NTIME(f)∩coNTIME(f)\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap...
Dalam [1] dinyatakan bahwa "Ini masih menjadi pertanyaan terbuka apakah setiap fungsi di memiliki sirkuit T C 0 (meskipun setidaknya diketahui bahwa tidak semua fungsi # P memiliki sirkuit T C 0 DLogTime-uniform-uniform )."#P#P\#PTC0TC0TC^0#P#P\#PTC0TC0TC^0 sirkuit yang dihasilkan oleh...
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...
Menurut Handshaking Lemma: setiap grafik tidak berarah yang memiliki simpul yang derajatnya adalah bilangan ganjil harus memiliki beberapa simpul lain yang derajatnya adalah bilangan ganjil. Pengamatan ini berarti bahwa jika kita diberi grafik dan simpul derajat ganjil, dan kita diminta untuk...
The isomorfisma Dugaan dari Berman dan Hartmanis menyatakan bahwa semua -Lengkap set waktu polinomial isomorfik satu sama lain. Ini berarti bahwa masalah lengkap dapat direduksi secara efisien satu sama lain melalui waktu polinomial yang dapat dihitung dan biopsi yang tidak dapat dibalik. Dugaan...
Saya mencari lebih banyak masalah di dengan kompleksitas waktu klasik batas bawah. Beberapa orang mungkin bertanya-tanya bagaimana Anda dapat membuktikan batas bawah seperti itu. Lihat di bawah.PPP Batas Bawah Eksponensial: Klaim: Jika Anda memiliki masalah yaitu -complete di bawah pengurangan...
Seperti yang ditunjukkan dalam makalah "Sirkuit Monoton untuk Fungsi Mayoritas", adalah mungkin untuk membangun sirkuit boolean monoton untuk fungsi mayoritas pada variabel n dengan ukuran O (n ^ 3) dan kedalaman 5,3 log (n) + O (1).
Saya mungkin kehilangan sesuatu yang jelas tetapi saya tidak dapat menemukan referensi tentang kompleksitas penghitungan pencocokan (bukan pencocokan sempurna) dalam grafik bipartit. Inilah masalah formal: Input: grafik bipartit denganG=(U,V,E)G=(U,V,E)G = (U, V, E)E⊆U×VE⊆U×VE \subseteq U \times...
Pertimbangkan masalah keputusan berikut. Biarkan dan biarkan (C_0 ^ n, C_1 ^ n, \ dots, C_ {q-1} ^ n) menjadi cocok enumerasi himpunan bagian dari \ {0,1, \ dots, n-1 \} yang memiliki paling banyak n / 4 elemen.q=∑n/4i=0(ni)q=∑i=0n/4(ni)q = \sum_{i=0}^{n/4}
Dalam tulisan ini , Hajnal menyatakan lemma berikut: Misalkan Gn,mGn,m\mathscr{G}_{n, m} adalah himpunan semua grafik bipartit dengan simpul di bagian kiri dan simpul di bagian kanan. Misalkan adalah nontrivial, monoton, dan invarian terkait dengan isomorfisme grafik bipartit. Pesan rangkaian...
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...
Apakah #P pertama kali diperkenalkan di [1] ? [1] Valiant, Leslie G. "Kompleksitas komputasi yang permanen." Ilmu komputer teoretis 8.2 (1979):
Misalkan . Kemudian argumen sederhana menunjukkan bahwa P H P P = N P . Bisakah kita melangkah lebih jauh dan mendapatkan P P P P = N P ? Argumen sederhananya adalahNP= PPNP=PPNP=PPPHPP= NPPHPP=NPPH^{PP}=NPPPPP= NPPPPP=NPPP^{PP}=NP Teorema Jika maka P H P P = N P .NP= PPNP=PPNP=PPPHPP=...
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...
Savický dan Woods (Jumlah Fungsi Boolean Dihitung dengan Rumus dari Ukuran yang Diberikan) membuktikan hasil berikut. Teorema [SW98]: Untuk setiap konstan , hampir semua fungsi boolean dengan kompleksitas rumus paling n k memiliki kompleksitas rangkaian setidaknya n k / k
Masalah umum Misalkan kita memiliki fungsi polinomial multivariat , dan beberapa fungsi linear ℓ i ( x ) . Apa yang diketahui tentang kompleksitas penyelesaian masalah pengoptimalan berikut?f( x )f(x)f(\mathbf{x})ℓi(x)ℓi(x)\ell_i(\mathbf{x}) MaximizeSubject to: f(x)ℓi(x)≤0 for...