Makalah Fischer bulan ini mengingatkan saya betapa sedikit yang saya tahu tentang seni struktur data yang ringkas, dan algoritma untuk menggunakannya. Bagi mereka yang tidak tahu tentang struktur data ringkas: Diberikan struktur kombinatorial, dengan (n) konfigurasi berbeda, dan representasi...
Seperti diketahui, PARITY tidak dapat dilakukan di sirkuit dengan kedalaman konstan berukuran poli, dan pada kenyataannya sirkuit dept membutuhkan jumlah gerbang EXP. Bagaimana dengan sirkuit QUANTUM? a) Dapatkah PARITY dilakukan dengan sirkuit kuantum yang memiliki kedalaman konstan dan jumlah...
Saya mengerti bahwa kelengkapan Turing membutuhkan memori tanpa batas dan waktu tanpa batas. Namun ada sejumlah atom dalam layanan ini sehingga membuat memori dibatasi. Sebagai contoh meskipun tidak rasional, tidak ada cara untuk menyimpan lebih dari jumlah digit tertentu bahkan jika semua atom...
Dengan diberikan grafik asiklik terarah, , mungkinkah mendukung operasi berikut secara efisien?G(V,E)G(V,E)G(V,E) : Menentukan apakah ada jalur dalam G dari simpul a ke simpulisConnected(G,a,b)isConnected(G,a,b)isConnected(G,a,b)GGGaaabbb : Menambahkan tepi dari a ke b dalam grafik...
Bagaimana jika ada yang diketahui tentang kompleksitas parameter dari penghitungan angka perpotongan grafik (jumlah klik terkecil yang diperlukan untuk menutupi semua tepinya)? Sudah lama dikenal sebagai NP-complete, dan itu jelas FPT karena memiliki kernel: jika Anda dapat menutupi grafik dengan...
Gagasan saya tentang karier impian adalah karier dalam penelitian industri, di mana seseorang dapat mengatasi masalah yang menantang, dan juga memiliki penggunaan praktis. Untuk itu, apakah mengejar gelar PhD di TCS (saya tertarik pada topik seperti algoritma yang didistribusikan / paralel,...
bagaimana seseorang dapat menunjukkan bahwa apa hubungan antara "dugaan game unik" dan "teorema PCP"? bagaimana orang menjelaskan "Dugaan game unik" adalah bentuk yang lebih kuat dari "teorema
Dalam teori automata (automata terbatas, automata pushdown, ...) dan dalam kompleksitas, ada gagasan "ambiguitas". Otomat bersifat ambigu jika ada kata www dengan setidaknya dua proses penerimaan yang berbeda. Sebuah mesin kkk ambigu jika untuk setiap kata www diterima oleh mesin paling tidak ada...
Saya mencari contoh mudah dari dua sistem transisi yang setara LTL, tetapi tidak setara jejak. Saya telah membaca bukti Trace Equivalence yang lebih baik daripada LTL Equivalence dalam buku "Principles of Model Checking" (Baier / Katoen) tapi saya tidak yakin saya benar-benar memahaminya. Saya...
Komputasi berlebihan mengacu pada model komputasi yang tidak mungkin untuk disimulasikan menggunakan mesin Turing. (Hypercomputer belum tentu dapat direalisasikan secara fisik!) Beberapa hypercomputer memiliki akses ke sumber daya yang memungkinkan Masalah Pemutusan untuk mesin Turing standar dapat...
Sudah diketahui umum bahwa jika Anda melempar n bola ke dalam n bin, nampan yang paling banyak dimuat kemungkinan besar memiliki O ( logn )HAI(catatann)O(\log n) bola di dalamnya. Secara umum, orang dapat bertanya tentang m > nm>nm > n bola dalam nnn nampan. Sebuah makalah dari RANDOM 1998...
Saya telah diberitahu bahwa ada beberapa waktu algoritma polinomial baik untuk mendekati jumlah jalur sederhana dalam grafik diarahkan dari yang diberikan mulai vertex untuk diberikan berakhir vertex . Adakah yang tahu referensi yang bagus tentang hal ini?sssttt Latar belakang: menghitung jumlah...
Saya memiliki dua partisi [1…n][1…n][1 \ldots n] dan saya mencari jarak sunting di antara mereka. Dengan ini, saya ingin menemukan jumlah minimal satu transisi dari sebuah node ke grup yang berbeda yang perlu beralih dari partisi A ke partisi B. Misalnya jarak dari {0 1} {2 3} {4}ke {0} {1} {2 3...
Metode musuh negatif ( A D V±SEBUAHDV±ADV^\pm ) adalah SDP yang mencirikan kompleksitas kueri kuantum. Ini adalah generalisasi dari metode permusuhan yang banyak digunakan ( A D VSEBUAHDVADV ), dan mengatasi dua penghalang yang menghalangi metode permusuhan: Hambatan pengujian properti: jika...
Saya baru-baru ini membaca bukti yang dimaksudkan untuk menunjukkan bahwa masalah adalah NP-hard sangat, hanya dengan mengurangi itu (dalam waktu polinomial) dari masalah NP-hard. Ini tidak masuk akal bagi saya. Saya akan berpikir bahwa Anda harus menunjukkan bahwa angka apa pun yang digunakan...
Baru-baru ini saya berada di sebuah konferensi yang didukung ACM. Selama jamuan makan, panitia konferensi memberi tahu kami tentang masa depan dan masa lalu konferensi. Mereka memberi tahu kami bahwa selama konferensi edisi 2010 ada kerugian $ 5.000. Mereka menunjukkan kepada kami anggaran...
Apa metode yang paling dikenal untuk konvolusi siklik dengan panjang atas bidang kecil, yaitu ketika | F | ≪ n ? Saya sangat tertarik pada bidang berukuran konstan, atau bahkan F = F 2 . Pernyataan dan referensi efisiensi asimptotik umum sangat dihargai.nnn| F | ≪n|F|≪n|\mathbb{F}| \ll nF =...
Penggoda Karena masalahnya gondrong di sini adalah kasus khusus yang menangkap esensinya. Masalah: Misalkan A menjadi algoritme detrministik untuk 3-SAT. Apakah masalah sepenuhnya mensimulasikan algoritma A (pada setiap contoh masalah). P-Space keras? (Lebih tepatnya, apakah ada alasan untuk...
SSS adalah seperangkat poin di pesawat. Titik acak diberikan pada bidang yang sama. Tugasnya adalah untuk mengurutkan semua dengan jarak Euclidean antara dan .x∉Sx∉Sx \notin Sy∈Sy∈Sy \in Sxxxyyy Pendekatan tanpa otak adalah menghitung jarak antara dan untuk semua dan kemudian mengurutkannya...
Pertanyaan ini mirip dengan salah satu pertanyaan saya sebelumnya. Hal ini diketahui bahwa adalah minor dilarang untuk grafik dari treewidth paling t .Kt + 2Kt+2K_{t+2}ttt Adakah keluarga yang dibangun dengan baik, parameter, dan tak terbatas grafik (selain grafik lengkap dan grafik kisi) yang...