pertanyaan umum tentang memilih elemen terbaik dari sejumlah alternatif yang tersedia.
Saya agak bingung dengan literatur optimasi kontinu dan literatur TCS tentang jenis program matematika (MP) yang dapat diselesaikan secara efisien, dan yang tidak. Komunitas optimisasi berkelanjutan tampaknya mengklaim bahwa semua program cembung dapat diselesaikan secara efisien, tetapi saya yakin...
Dalam pendidikan ilmu komputer saya, saya semakin memperhatikan bahwa sebagian besar masalah diskrit adalah NP-lengkap (setidaknya), sedangkan mengoptimalkan masalah terus menerus hampir selalu mudah dicapai, biasanya melalui teknik gradien. Apakah ada pengecualian untuk
Apa yang diketahui tentang kompleksitas masalah berikut: Diberikan: bilangan rasional .x1<x2<…<xnx1<x2<…<xnx_1 < x_2 < \dotso < x_n Output: bilangan bulat .y1≤y2≤…≤yny1≤y2≤…≤yny_1 \le y_2 \le \dotso \le y_n Tujuan: kecilkan mana∑1≤i<j≤ne(i,j),∑1≤i<j≤ne(i,j),\sum_{1 \le i <...
Komputer kuantum sangat baik untuk distribusi sampel yang kita tidak tahu bagaimana sampel menggunakan komputer klasik. Sebagai contoh jika f adalah fungsi Boolean (dari hingga ) yang dapat dihitung dalam waktu polinomial maka dengan komputer kuantum kita dapat secara efisien sampel sesuai dengan...
Saya tertarik pada masalah pengemasan salinan identik persegi panjang (2 dimensi) menjadi cembung (2 dimensi) poligon tanpa tumpang tindih. Dalam masalah saya, Anda tidak diperbolehkan memutar persegi panjang dan dapat mengasumsikan bahwa mereka berorientasi paralel dengan sumbu. Anda hanya diberi...
Pertimbangkan masalah pengoptimalan dari formulir berikut. Misalkan f(x)f(x)f(x) menjadi fungsi yang dapat dihitung polinomial-waktu yang memetakan string menjadi bilangan rasional. Masalah optimasinya adalah ini: berapakah nilai maksimum atas bit string ?f ( x ) nxxxf(x)f(x)f(x)nnnxxx Mari kita...
Kode Huffman untuk distribusi probabilitas adalah kode awalan dengan panjang codeword rata-rata tertimbang minimum , di mana adalah panjang dari kata sandi ke- . Ini adalah teorema yang terkenal bahwa panjang rata-rata per simbol kode Huffman adalah antara dan , di mana adalah entropi Shannon dari...
Seperti kita ketahui, fungsi -clique C L I Q U E ( n , k ) mengambil subgraph ( spanning ) G ⊆ K n dari grafik n -vertex lengkap K n , dan menghasilkan 1 iff G berisi k -clique . Variabel dalam hal ini sesuai dengan tepi dari K n . Sudah diketahui (Razborov, Alon-Boppana) bahwa, selama 3 ≤ k ≤ n /...
Anda diberi grafik dengan n simpul. Mungkin bipartit jika Anda mau. Ada m set tepi E 1 , … , E m ⊆ E (katakanlah disjoint). Saya tertarik pada masalah menemukan subset S ⊆ V , sekecil mungkin (atau bahkan lebih kecil), sehingga grafik yang diinduksi G S memiliki setidaknya satu sisi dari setiap...
Apakah mungkin untuk menguji secara algoritmik apakah bilangan yang dihitung rasional atau bilangan bulat? Dengan kata lain, apakah mungkin bagi perpustakaan yang mengimplementasikan angka yang dapat dihitung untuk menyediakan fungsi isIntegeratau isRational? Saya menduga itu tidak mungkin, dan...
Anak saya yang berusia 8 tahun bosan membuat labirin konvensional, dan telah membuat varian yang terlihat seperti ini: Idenya adalah mulai dari x dan mencapai o melalui aturan normal. Selain itu, Anda dapat "hop" dari setiap bilangan bulat untuk setiap bilangan bulat lainnya b , tetapi Anda...
Pertimbangkan masalah ini: Diberikan daftar set yang terbatas, temukan pemesanan yang meminimalkan | s 1 | + | s 1 ∪ s 2 | + | s 1 ∪ s 2 ∪ s 3 | + … .s1,s2,s3,…s1,s2,s3,…s_1, s_2, s_3, \ldots|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| +...
Kita tahu bahwa program linier (LP) dapat diselesaikan tepat dalam waktu polinomial menggunakan metode ellipsoid atau metode titik interior seperti algoritma Karmarkar. Beberapa piringan hitam dengan jumlah variabel / kendala super-polinomial (eksponensial) juga dapat diselesaikan dalam waktu...
Bertahun-tahun yang lalu saya mendengar bahwa menghitung NFA minimal (otomat hingga nondeterministik) dari DFA (deterministik) adalah pertanyaan terbuka, berlawanan dengan arah sebaliknya yang telah dikenal selama beberapa dekade dan diteliti dengan baik dengan efisien algoritma. Adakah yang datang...
Pertimbangkan masalah berikut: Input : hyperplane H = { y ∈ R n : a T y = b }H={y∈Rn:aTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\} , diberikan oleh vektor dan dalam representasi biner standar .a ∈ Z na∈Zn\mathbf{a} \in \mathbb{Z}^n b ∈ Zb∈Zb \in \mathbb{Z} Output :x ∈ Z...
Saya telah menanyakan pertanyaan ini pada Stack Overflow beberapa waktu lalu: Masalah: Penjualan Bob . Seseorang menyarankan untuk mengirim pertanyaan di sini juga. Seseorang telah mengajukan pertanyaan terkait dengan masalah ini di sini - Berat minimum hutan hujan dari kardinalitas yang diberikan...
Apa kompleksitas komputasi untuk mengoptimalkan berbagai fungsi di atas grup kesatuan ?U( n )U(n)\mathcal{U}(n) Sebuah tugas yang khas, yang timbul sering dalam teori informasi kuantum, akan memaksimalkan kuantitas tipe (atau perintah polinomial lebih tinggi di U ) atas semua kesatuan matriks U ....
Pertimbangkan ruang nnn dimensi {0,1}n{0,1}n\{0,1\}^n , dan mari menjadi batasan linear dari bentuk , di mana , dan .ccca1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq kai∈Rai∈Ra_i \in...
Saya sedang menyiapkan beberapa materi kursus tentang heuristik untuk optimisasi, dan telah mencari metode penurunan koordinat. Pengaturan di sini adalah fungsi multivarian yang ingin Anda optimalkan. memiliki properti yang terbatas pada variabel tunggal mana pun, mudah dioptimalkan. Jadi...
Baru-baru ini saya tertarik pada masalah umum dalam mengoptimalkan penggunaan memori dalam situasi di mana ada lebih dari satu jenis memori yang tersedia, dan ada pertukaran antara kapasitas segmen memori yang diberikan dan kecepatan mengaksesnya. Contoh yang umum adalah program memutuskan kapan...