Saya telah berupaya memperkenalkan beberapa hasil dari kompleksitas komputasi ke dalam biologi teoretis, terutama evolusi & ekologi , dengan tujuan menjadi menarik / berguna bagi para ahli biologi. Salah satu kesulitan terbesar yang saya hadapi adalah membenarkan kegunaan analisis kasus...
semua orang tahu ada banyak masalah keputusan yang NP-keras pada grafik umum, tapi saya tertarik pada masalah yang bahkan NP-keras ketika grafik yang mendasari adalah jalan. Jadi, bisakah Anda membantu saya untuk mengumpulkan masalah seperti itu? Saya sudah menemukan pertanyaan terkait tentang...
Banyak masalah grafik algoritmik dapat diselesaikan dalam waktu polinomial baik pada grafik tidak tertimbang dan berbobot. Beberapa contoh adalah lintasan terpendek, pohon spanning min, lintasan terpanjang (dalam grafik asiklik langsung), aliran maks, min cut, pencocokan maks, arborescence optimal,...
Ini semacam pertanyaan terbuka - yang sebelumnya saya minta maaf. Apakah ada contoh pernyataan yang (tampaknya) tidak ada hubungannya dengan kompleksitas atau mesin Turing tetapi jawabannya akan menyiratkan ?P≠NPP≠NP\mathbf{P}\neq
Menyusul dari pertanyaan sebelumnya , apa batas bawah ruang terbaik saat ini untuk SAT? Dengan batas bawah ruang yang saya maksud di sini adalah jumlah sel worktape yang digunakan oleh mesin Turing yang menggunakan alfabet biner worktape. Istilah aditif konstan tidak dapat dihindari karena TM...
Dalam makalah "KOMPLEKSITAS MASALAH KEPUASAN" oleh Thomas J. Schaefer, penulis telah menyebutkan bahwa This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational...
Saya pernah membaca bahwa pada awalnya Gereja mengusulkan -calculus sebagai bagian dari postulat makalah Logic-nya (yang merupakan bacaan padat). Tetapi Kleene membuktikan "sistem" -nya tidak konsisten setelah itu, Gereja mengekstraksi hal-hal yang relevan untuk karyanya tentang "komputabilitas...
Saya sedang membaca makalah Andrej Bauer Langkah Pertama dalam Teori Komputasi Sintetis . Dalam kesimpulan dia mencatat itu Aksiomasiisasi kami memiliki batas: tidak dapat membuktikan hasil apa pun dalam teori komputabilitas yang gagal dikaitkan dengan perhitungan oracle. Ini karena teori dapat...
Dalam utas ini , percobaan Norbet Blum dengan singkat dibantah dengan mencatat bahwa fungsi Tardos adalah contoh tandingan terhadap Teorema 6.P≠ NPP≠NPP \neq NP Teorema 6 : Biarkan menjadi fungsi Boolean monoton. Asumsikan ada CNF-DNF-approximator yang dapat digunakan untuk membuktikan batas bawah...
Biarkan variabel menjadi . Jarak antara dua variabel didefinisikan sebagai. Jarak antara dua literal adalah jarak antara dua variabel yang sesuai.x1,x2,x3...xnx1,x2,x3...xnx_1 , x_2 , x_3 ... x_nd(xa,xb)=|a−b|d(xa,xb)=|a−b|d(x_a , x_b) = |a-b| Misalkan saya memiliki instance 3-SAT sehingga untuk...
Apakah ada survei yang baik yang membandingkan berbagai ekstraktor, konsentrator dan superconcentrator dan menjabarkan metode terbaik dalam hal tradeoff antara keacakan, waktu dan ruang?
Bukti pemisahan kelas kompleksitas menggunakan keseragaman kelas kompleksitas pada dasarnya jika bukti tidak membuktikan hasil untuk versi tidak seragam, misalnya bukti yang didasarkan pada diagonalisasi (seperti teorema hierarki ruang dan waktu) membuat penggunaan penting keseragaman karena mereka...
Kita tahu banyak tentang batasan-batasan (kedalaman polinomial) sirkuit-konstan. Karena (kedalaman polinomial) rumus kedalaman konstan adalah model perhitungan yang bahkan lebih terbatas, semua masalah yang diketahui tidak ada dalam AC 0 juga tidak dapat dihitung dengan rumus kedalaman konstan....
Apa perbedaan menarik yang ada antara teori dan praktik keamanan dan kriptografi? Paling menarik tentu saja akan menjadi contoh yang menunjukkan jalan baru untuk penelitian teoritis berdasarkan pengalaman praktis :). Jawaban mungkin termasuk (tetapi tidak terbatas pada): Contoh di mana teori...
Jika adalah fungsi cembung maka ketidaksetaraan Jensen menyatakan bahwa , dan saling mutatis ketika adalah cekung. Jelas dalam kasus terburuk Anda tidak bisa menggunakan batas atas dalam hal untuk cembung , tetapi apakah ada batas yang mengarah ke arah ini jika adalah cembung tetapi "tidak terlalu...
Saya sudah memposting pertanyaan ini beberapa waktu yang lalu di MathOverflow , tapi sejauh pengetahuan saya masih terbuka, jadi saya memposting ulang di sini dengan harapan bahwa seseorang mungkin pernah mendengarnya. Pernyataan masalah Misalkan , Q dan R menjadi tiga partisi menjadi p bagian...
Adakah yang bisa menunjuk ke satu atau lebih situs web di mana dimungkinkan untuk mengunduh implementasi kerja pemecah #SAT? Saya tertarik pada mereka yang mengembalikan hitungan solusi yang tepat, bukan
Apakah BQP sama dengan BPP dengan akses ke subkelompok tersembunyi
Ketika menyusun hasil, sering diinginkan untuk memiliki beberapa diagram yang terlihat profesional, daripada diagram yang disatukan dalam MS Paint. Apa standar untuk menggambar struktur
(Von Neumann memberikan algoritma yang mensimulasikan koin yang adil diberikan akses ke koin bias identik. Algoritma ini berpotensi membutuhkan jumlah koin yang tak terbatas (meskipun dalam harapan, cukup banyak saja). Pertanyaan ini menyangkut kasus ketika jumlah lemparan koin yang diizinkan...