Saya punya pertanyaan, yang jawabannya mungkin terkenal, tetapi saya tidak bisa menemukan sesuatu yang berarti setelah sedikit pencarian, jadi saya sangat menghargai bantuan. Pertanyaan saya adalah apakah diketahui bahwa memutuskan apakah suatu angka bersifat transendental tidak dapat diputuskan....
Adakah hasil yang diketahui tentang kerumitan menemukan pemisah (dalam ukuran apa pun) yang memuaskan properti tertentu? Saya tahu bahwa pemisah klik mudah (waktu polinomial) untuk menemukan dan juga tahu bahwa banyak makalah mempertimbangkan masalah menemukan pemisah kecil atau pemisah yang...
Ada sebuah program linier yang saya inginkan bukan hanya solusi tetapi solusi yang sangat sentral di muka polytope yang mengasumsikan nilai minimal. Secara apriori, kami berharap wajah meminimalkan harus berdimensi tinggi karena berbagai alasan, termasuk bahwa fungsi objektif yang diminimalkan...
Di Graphic TSP , Anda diberi grafik tidak diarahkan dan tujuannya adalah untuk menemukan tur terpendek di G yang mengunjungi setiap titik setidaknya satu kali . Catatan bahwa ini adalah tidak sama dengan menemukan sirkuit Hamilton di G . Pertanyaan saya adalah:GGGGGGGGG Apa kompleksitas TSP...
Misalkan adalah grafik yang tertanam pada permukaan kompak genus g yang dapat diorientasikan sehingga embedding bersifat seluler. Pertimbangkan dual dari grafik G ∗ . Biarkan C 1 dan C 2 menjadi siklus terpisah dalam G ∗ yang saling homotopik dan biarkan E 1 dan E 2 menjadi set tepi yang sesuai di...
Saya mencari dimensi VC dari sistem set berikut. Universe sedemikian rupa sehingga U ⊆ R 3 . Dalam sistem himpunan R, setiap himpunan S ∈ R berkorespondensi dengan sphere dalam R 3 sehingga himpunan S mengandung elemen dalam U jika dan hanya jika sphere yang sesuai berisinya dalam R 3 .U= { p1,...
Dalam pertanyaan sebelumnya. Algoritma Parametrized untuk Menemukan Bicliques , saya bertanya apakah ada algoritma parametrized cepat untuk menemukan biclique dalam grafik n vertex dan mengetahui bahwa itu terbuka jika FPT wrt k . Adalah benar sama untuk menghitung para k × k -bicliques, atau itu...
Saya ingin meminta maaf kepada semua posting di bawah ini. Memilih forum yang salah untuk memposting ini pada awalnya. Namun alih-alih membuat ini sia-sia saya telah mengolah pertanyaan menjadi masalah "Theoretical Computer Science" yang sebenarnya. Masalah: Buat algoritme yang mengambil...
Biarkan menjadi satuan persegi. Sebagai fungsi dari , berapakah jumlah maksimum dari -fat berpasangan-berpisah dengan diameter setidaknya 1 yang dapat memotong ?SSSββ\betaββ\betaSSS Di bawah, kami memberikan angka yang menunjukkan bahwa untuk , jumlah maksimumnya adalah 7. Bagaimana dengan...
Ada beberapa masalah NP-Lengkap ( , S U B S E T S U M , dll.) Diketahui berada di D S P A C E ( n ) . Bagaimana dengan ruang sub-linear?SATSAT \mathsf{SAT} SUBSETSUMSUBSETSUM \mathsf{SUBSETSUM} DSPACE(n)DSPACE(n) \mathsf{DSPACE(n)} Apakah ada masalah NP-Complete (atau NP-Intermediate) yang...
Per judul, selain menggunakan LP solver tujuan umum, apakah ada pendekatan untuk memecahkan sistem ketidaksetaraan atas variabel mana ketidaksetaraan memiliki bentuk ? Bagaimana dengan kasus khusus ketidaksetaraan yang membentuk urutan total atas jumlah anggota set daya ?∑ i ∈ I x i < ∑ j ∈ J x...
Ini adalah pertanyaan yang saya ajukan di forum SE matematika, dan saya dirujuk di sini. Jadi di sini adalah pertanyaan- Saya seorang pemula di kedua matematika formal dan ilmu komputer teoretis, jadi silakan bersamaku jika Anda menemukan pertanyaan saya tidak dibingkai dengan benar. Pemodelan...
Misalkan kita memiliki grafik pada nnn node. Kami ingin menetapkan ke setiap node baik + 1+1+1 atau . Sebut ini sebagai konfigurasi . Jumlah yang harus kita tetapkan adalah persis (karenanya jumlah dt adalah .) Dengan konfigurasi , kita melihat setiap simpul dan menjumlahkan nilai yang diberikan...
Saya mencari teorema yang mengatakan sesuatu seperti ini: jika waktu tutup rantai Markov reversibel kecil, maka celah spektral besar. Di sini celah spektral berarti 1 - | λ2|1-|λ2|1-|\lambda_2|, yaitu, kami mengabaikan nilai eigen terkecil dari rantai. O ( n logn )HAI(ncatatann)O(n \log n)1 -...
Sunting: sekarang ada pertanyaan lanjutan yang terkait dengan pos ini. Definisi Biarkan ccc dan kkk menjadi bilangan bulat. Kami menggunakan notasi [ I ] = { 1 , 2 , . . . , saya }[saya]={1,2,...,saya}[i] = \{1,2,...,i\} . Sebuah c × cc×cc \times c matriks M.= ( msaya , j)M.=(msaya,j)M =...
Saya telah menanyakan masalah ini di MathOverflow , tanpa jawaban yang memuaskan. Pertimbangkan permainan dua pemain berikut ini, yang merupakan penyederhanaan dari permainan kartu yang disebut Winner . (Formulasi berikut diambil dari komentar oleh Guillaume Brunerie di MathOverflow.) Ada dua...
Saya mencari algoritme untuk menggambar grafik gabungan / ketergantungan (untuk aplikasi linguistik). Grafik seperti itu akan memiliki dua jenis simpul yang berbeda (token, node), dan dua jenis tepi yang berbeda (hierarkis, non-hierarkis). Saya baru mengenal teori grafik dan algoritma secara umum,...
Saya telah berjuang dengan rincian teknis bukti tentang teori lelang dalam makalah ini: http://users.eecs.northwestern.edu/~hartline/omd.pdf Secara khusus, Teorema 2.5: Kondisi yang diperlukan dan cukup untuk mekanisme yang benar. Bahkan lebih spesifik, arah maju buktinya, diberikan pada halaman...
Saya bekerja di bidang teknik struktural dan saya ingin menemukan algoritma yang efisien untuk membangun perkiraan (dalam metrik Hausdorff) dari tubuh cembung KKK oleh cembung cembung ellipsoid, untuk beberapa tetap . Saat ini saya hanya bekerja di dimensi 2 dan 3.nnnnnn Gagasan pertama saya...
Background––––––––––––––Background_\underline{\bf Background} Pada tahun 2005, Regev [1] memperkenalkan masalah Learning with Errors (LWE), generalisasi dari Learning Parity with Error error. Asumsi kekerasan masalah ini untuk pilihan parameter tertentu sekarang mendasari bukti keamanan untuk...