Apa saja contoh masalah yang diketahui berada dalam AMAM\mathsf{AM} (resp. MAMA\mathsf{MA} ) yang tidak diketahui berada dalam NPNP\mathsf{NP} atau dalam BPPBPP\mathsf{BPP} ? Untuk AMAM\mathsf{AM} , saya tahu dua contoh berikut: Grafik non-isomorfisme: Diberikan dua grafik berlabel GGG dan HHH ,...
Diberikan tabel data yang mengandung jumlah baris yang sangat besar , dengan setiap baris berisi sejumlah besar k bidang, dengan setiap bidang berisi sejumlah bit yang besar tetapi tetap, ada sejumlah metode untuk membangun struktur "indeks" sehingga bahwa operasi berikut dapat dilakukan pada tabel...
Saya telah melihat logika modal dengan aksioma ( ◊ A ∧ ◊ B ) → ◊ ( ( A ∧ ◊ B ) ∨ ( A ∧ B ) ∨ ( A ∧ ◊ B ) )(◊SEBUAH∧◊B)→◊((SEBUAH∧◊B)∨(SEBUAH∧B)∨(SEBUAH∧◊B)) (\Diamond A \land \Diamond B) \to \Diamond((A \land \Diamond B) \vee (A \land B) \vee (A \land \Diamond B)) Secara kasar, ini mengatakan...
Katakanlah Anda memiliki sejumlah set bilangan bulat ( ), dan Anda ingin menghitung persimpangan dari beberapa dari mereka ( ∩ S 1 , S 3 , S 7 mungkin query, tetapi Anda ingin untuk mendukung banyak pertanyaan seperti itu, atau bahkan mungkin semua pertanyaan yang mungkin)S1,S2...SnS1,S2...SnS_1,...
Saya memiliki satu set agen dan satu set n tugas, dan saya perlu menetapkan masing-masing agen dengan tepat satu tugas sehingga biaya diminimalkan. Beberapa agen tidak kompatibel dengan beberapa tugas.nnnnnn Saya memiliki implementasi Algoritma Hongaria yang membutuhkan waktu sekitar satu menit...
Masalah kepuasan maksimum (Max-Sat) adalah masalah menemukan jumlah klausa maksimum yang dapat dipuaskan dalam contoh kepuasan Boolean. The tepat 1 di 2 masalah Sat bertanya, diberikan satu set klausa masing-masing dengan dua literal, ada satu set literal sehingga setiap klausul memiliki tepat satu...
Diberikan bilangan aljabar , saya tertarik untuk menemukan perkiraan ℜ ( e α ) hingga presisi yang diberikan, di mana ℜ ( ) mengacu pada bagian nyata dari bilangan kompleks.αα\alphaR(eα)ℜ(eα)\Re(e^\alpha)R()ℜ()\Re() Secara formal, saya ingin menghitung bilangan rasional sehingga | ℜ ( e α ) - r...
Sebagian besar sumber daya mengenai pengertian kategoris dalam pemrograman menggambarkan monad, tetapi saya belum pernah melihat deskripsi kategorik dari monad transformer. Bagaimana transformator monad dijelaskan dalam istilah teori kategori? Secara khusus, saya akan tertarik pada: hubungan...
Ketika kami mencoba membuat algoritma untuk masalah baru, bagi-dan-taklukkan (menggunakan rekursi) adalah salah satu pendekatan pertama yang kami coba. Tetapi dalam beberapa kasus, pendekatan ini tampaknya tidak membuahkan hasil karena masalahnya menjadi jauh lebih rumit ketika inputnya...
Apakah ada semantik kategoris untuk logika non-monotonik? Tampaknya jawaban sederhana untuk ini adalah "Tidak" karena gagasan jelas tentang komposisi gagal untuk model logika non-monotonik apa pun. Tetapi apakah ada model yang benar-benar berfungsi dengan gagasan komposisi yang didefinisikan...
Pertanyaan saya berkaitan dengan bukti teorema utama Ajtai dalam makalahnya yang inovatif pada tahun 1996, Menghasilkan contoh-contoh sulit dari masalah kisi , yang menunjukkan hubungan antara masalah kisi hard case terburuk dan hard case rata-rata. Bukti ini sulit bagi saya untuk mengerti. Apakah...
Ada beberapa teorema, kebanyakan dalam teori grafik dan optimasi kombinatorial, yang sering disebut sebagai penokohan yang baik. Mereka biasanya menempatkan properti di , dengan menunjukkan bahwa suatu properti dapat bertahan, atau ada beberapa kendala yang teridentifikasi dengan baik yang...
Menurut XOR Satisfiability Solver Module untuk Integrasi DPLL oleh Tero Laitinen, kita membutuhkan klausa CNF untuk mengubah klausa XOR-SAT literal jika kita tidak ingin menambah jumlah literal. Jadi, saya mengerti bahwa biaya komputasi untuk mengubah ekspresi XOR-SAT menjadi CNF -SAT adalah...
Saya telah mengerjakan proyek independen yang berfokus pada automata seluler dan bertanya-tanya apakah ini mungkin sesuatu yang bisa saya teruskan di sekolah pascasarjana di suatu tempat. Saya telah melihat beberapa departemen matematika dengan dinamika simbolis serta beberapa departemen CS dengan...
Asumsikan bahwa untuk masalah minimalisasi yang diberikan hanya dengan solusi integer, itu adalah -hard untuk memutuskan apakah solusi optimal adalah 5 atau 6. Yaitu, algoritma waktu polinomial dengan rasio perkiraan yang lebih baik dari 6/5 akan menyiratkan P = N P .NPNPNPP=NPP=NPP=NP 1) Apakah...
Grafik adalah bipartit lokal jika lingkungan terbuka dari setiap simpul menginduksi grafik bipartit. (Menurut penelusuran, nama yang sama dapat digunakan untuk hal lain yang terkait dengan permukaan). NP-hard untuk masalah grafik umum mana yang menjadi polinomial untuk grafik bipartit lokal dan...
Tampaknya bagi saya bahwa tugas penghapusan kuadrat dapat direduksi menjadi tugas anjak piutang , tetapi tidak ada cara untuk mengurangi anjak piutang menjadi penghapusan kuadrat. Apakah ada cara untuk membuat "perasaan" ini lebih tepat, yaitu beberapa hipotesis umum yang diyakini akan dilanggar...
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) \: < \:...
Saya melihat masalah ini: Sebuah peningkatan urutan non bilangan bulat positif m1,m2,...,mkm1,m2,...,mkm_1,m_2,..., m_k dikatakan n-realisasi jika set In={1,2,...,n}In={1,2,...,n}I_n=\{1,2,..., n\} dapat dibagi menjadi kkk saling himpunan bagian menguraikan S1,S2,...,SkS1,S2,...,SkS_1,S_2,...,S_k...
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...