Diberikan grafik terarah, kami ingin memutuskan apakah itu berisi siklus terarah dengan panjang genap. Makalah tahun 1997 oleh YUSTER dan ZWICK ini menyatakan bahwa masalahnya tidak diketahui dalam dan juga tidak diketahui lengkap.PPPNPNPNP Apakah ada hasil terbaru yang menyelesaikan...
Kita dapat melakukan konvolusi dalam untuk plus / multiplikasi polinomial dengan FFT. Namun, pendekatan itu tampaknya tidak terlalu umum untuk cincin pada umumnya. Apakah ada kemajuan selama konvolusi naif untuk cincin max / plus?O ( n logn )HAI(ncatatann)O(n\log n)O ( n2)HAI(n2)O(n^2) Saya harus...
Apakah ada 2DFA dengan negara (di mana n adalah non trivial, katakan setidaknya 4) yang membutuhkan setidaknya 2 negara n untuk mensimulasikan menggunakan DFA?nnnnnn2n2n2^n Sebuah dua arah DFA (2DFA) adalah deterministik finite-state automaton yang diperbolehkan untuk bergerak maju mundur pada...
Apakah masalah CNF SAT NP sulit ketika jumlah total (tetapi bukan lebar) dari klausa 3-atau-lebih istilah dibatasi di atas oleh konstanta? Bagaimana dengan spesifik ketika hanya ada satu klausa seperti
Otomat deterministik disebut k- lokal untuk k > 0 jika untuk setiap w ∈ X k himpunan { δ ( q , w ) : q ∈ Q } berisi paling banyak satu elemen. Secara intuitif itu berarti jika kata w dengan panjang k mengarah ke keadaan, maka keadaan ini unik, atau dikatakan berbeda dari kata panjang yang...
Diketahui bahwa untuk kesalahan definisi kasus terburuk dari kompleksitas komunikasi acak dan definisi kasus rata-rata adalah setara. Tetapi ketika kesalahannya adalah 0 , kompleksitas komunikasi acak kasus terburuk sama dengan kompleksitas komunikasi deterministik.Θ ( 1 )Θ(1)\Theta(1)000 Apakah...
Algoritma terdistribusi yang tahan terhadap kegagalan dapat bersifat deterministik atau probabilistik. Ambil contoh masalah konsensus. Paxos adalah deterministik dalam arti bahwa mengingat asumsi yang dibuatnya, ia selalu berhasil. Dalam konstrast, konsensus acak bekerja dengan probabilitas yang...
Dalam Bab 13 "Objek Atom" dari buku "Algoritma Terdistribusi" oleh Nancy Lynch, linearitas (juga dikenal sebagai atomisitas) terbukti menjadi properti yang aman. Dengan kata lain, properti jejak yang sesuai adalah nonempty, prefix-closed, dan limit-closed , sebagaimana didefinisikan dalam Bagian...
Algoritma polinomial-waktu dikenal untuk menemukan set yang menghasilkan kelompok permutasi, yang menarik karena kita kemudian dapat mewakili kelompok-kelompok tersebut secara ringkas tanpa menyerah pada algoritma polinomial-waktu untuk menjawab banyak pertanyaan menarik terkait dengan...
Minimisasi Sirkuit adalah masalah untuk meminimalkan ukuran sirkuit yang diberikan. Apakah ada yang serupa untuk program umum? Khususnya pertanyaan saya adalah - Apakah ada algoritma untuk meminimalkan # instruksi untuk program yang diberikan. Saya tahu ini masalah yang tidak dapat diputuskan,...
Kita tahu bahwa beta-equality dari istilah lambda yang diketik adalah mudah untuk dipilih. Diberikan M, N: σ → τ, apakah dapat ditentukan apakah untuk semua X: σ, MX ≃β≃β≃_β
Pertanyaan ini adalah tentang apakah ada tarpit Turing reversibel yang dikenal, di mana "reversibel" berarti dalam arti Axelsen dan Glück , dan "tarpit" adalah konsep yang jauh lebih informal (dan mungkin bukan pilihan kata yang sangat baik), tapi saya akan melakukan yang terbaik untuk menjelaskan...
Apakah ada kelas grafik yang bagus yang lebar pohon dibatasi oleh fungsi dari angka klik , yaitu ?t w ( G )tw(G)tw(G)ω ( G )ω(G)\omega(G)t w ( G ) ≤ f( ω ( G ) )tw(G)≤f(ω(G))tw(G)\leq f(\omega(G)) Sebagai contoh, ini adalah fakta klasik bahwa untuk setiap grafik chordal , kita memiliki . Jadi,...
Saya tertarik pada algoritma untuk grup hingga seperti yang diterapkan dalam paket GAP. Tampaknya semua algoritma yang dikenal dalam bidang ini berurusan dengan kelompok permutasi / kelompok matriks; dua yang mendasar adalah Schreier-Sims [1970] dan Butler [1979], lihat misalnya 'Algoritma untuk...
Ketidaksamaan Fano dapat dinyatakan dalam banyak bentuk, dan satu yang sangat berguna adalah karena (dengan sedikit modifikasi) kepada Oded Regev : Misalkan XXX adalah variabel acak, dan misalkan Y=g(X)Y=g(X)Y = g(X) mana g(⋅)g(⋅)g(\cdot) adalah proses acak. Asumsikan adanya prosedur fff yang...
Slackness komplementer (CS) umumnya diajarkan ketika berbicara tentang dualitas. Ini membangun hubungan yang bagus antara primal dan kendala ganda / variabel dari sudut pandang matematika. Dua alasan utama untuk menerapkan CS (seperti yang diajarkan di kursus pascasarjana dan buku teks): Untuk...
Untuk sementara waktu sekarang, saya sangat tertarik dengan teori bahasa pemrograman dan proses kalkulus dan sudah mulai mempelajarinya. Sejujurnya, itu adalah sesuatu yang saya tidak keberatan untuk berkarier. Saya menemukan teorinya sangat menarik. Satu pertanyaan konstan yang terus saya temui...
Saya menemukan masalah terbuka yang diajukan oleh David Eppstein dan saya tertarik dengan status kompleksitasnya. Dia menduga itu NP-lengkap. Input: oleh n matriks 0's dan 1's, urutan n 2 0's dan 1'snnnnnnn2n2n^2 Pertanyaan: Apakah ada jalur melalui entri matriks yang berdekatan, yang mencakup...
Diberikan dua polyhedra dan Q , P dan Q sama-sama dapat dikomposisikan jika ada set polyhedra P 1 yang terbatas , ... , P n dan Q 1 , ... , Q n sedemikian rupa sehingga P i dan Q i kongruen untuk semua i , P = ∪ n i = 1 P i dan Q = ∪ n i = 1 QPPPQQQPPPQQQP1,…,PnP1,…,PnP_1, \ldots,...
Mari kita sebut bahasa NP yang jarang memiliki sertifikat jika dan hanya jika:L ∈L∈L \in Ada polinomial sedemikian rupa sehingga untuk setiap input ukuran , jika maka set sertifikat yang memverifikasi bahwa berukuran polinomially, yaitu . x ∈ Σ ∗ n x ∈ L U x u x ∈ L | U x | ≤ p ( n )p : N →...