sering dikatakan bahwa ketika menggunakan algoritme MD5 untuk menandatangani beberapa informasi sewenang-wenang, rahasia bersama harus ada di akhir.
Dua puluh tahun yang lalu, saya membangun paket ekspresi reguler yang mencakup konversi dari ekspresi reguler ke mesin keadaan terbatas (DFA) dan mendukung sejumlah operasi ekspresi reguler tertutup (bintang Kleene, penggabungan, pembalikan, set operasi, dll). Saya tidak yakin tentang kinerja...
Untuk bahasa L ⊆ Σ ^ * , tentukan kongruensi sintaksis ≡ dari L sebagai kongruensi terkecil pada on ^ * yang menjenuhkan L , yaitu: u ≡ v ⇔ (∀ x, y) [xuy ∈ L ↔ xvy ∈ L]. Sekarang tentukan kesetaraan Nerode sebagai kongruensi kanan berikut: u ∼ v ⇔ (∀ x) [ux ∈ L ↔ vx ∈ L]. Biarkan [u] menjadi...
Ini adalah tindak lanjut dari pertanyaan ini di math.stackexchange. Mari kita katakan bahwa himpunan non-kosong S ⊆ ℤ adalah swadaya jika untuk setiap a ∈ S, terdapat elemen yang berbeda b, c ∈ S sedemikian rupa sehingga a = b + c. Untuk bilangan bulat positif n , contoh sederhana termasuk S...
Adleman, FOCS'78 menunjukkan bahwa setiap rangkaian acak untuk input dengan panjang dapat tidak dereragamkan. Namun, konstruksi secara efektif menduplikasi sirkuit asli O ( n ) kali, sehingga sirkuit derandomisasi lebih besar dari yang asli dengan faktor O ( n ) . Apakah ada konstruksi yang lebih...
Dalam [1], Turan menunjukkan bahwa sensitivitas (disebut "kompleksitas kritis" di kertas) properti grafik benar-benar lebih besar dari manamadalah jumlah simpul dalam grafik. Dia melanjutkan dengan dugaan bahwa setiap properti grafik non-sepele memiliki sensitivitas≥m-1. Dia menyebutkan bahwa ini...
Seperti di, area makalah dalam Jurnal ACM tentang Experimental Algorithmic JEA . Yang merupakan karya dasar? Apa hasil utamanya? Bagaimana mereka dikarakterisasi? Adakah koneksi menarik ke bidang ilmu komputer
Gambar Dunia yang terkenal dari Neil Immerman adalah sebagai berikut (klik untuk memperbesar): Kelasnya "Benar-benar layak" tidak termasuk kelas lain; pertanyaan saya adalah: Apa masalah AC 0 yang dianggap tidak taktis, dan...
The titik -Tetap masalah automorphism bebas meminta grafik automorphism yang bergerak setidaknya node. Masalahnya adalah -complete jika untuk > 0.kkkN P k ( n ) = n c ck(n)k(n)k(n)NPNPNPk(n)=nck(n)=nck(n)=n^cccc Namun, jika maka masalahnya adalah waktu polinomial Turing yang dapat direduksi...
LogCFL adalah himpunan semua bahasa yang logspace direduksi menjadi bahasa bebas konteks. Demikian pula, LogDCFL adalah himpunan semua bahasa yang logspace direduksi menjadi bahasa bebas konteks deterministik. Lihat artikel wikipedia ini untuk beberapa masalah lengkap LogCFL. Ada beberapa masalah...
Satu celah yang saya selalu sadar bahwa saya tidak benar-benar mengerti adalah antara kompleksitas komputasi tidak seragam dan seragam di mana kompleksitas sirkuit mewakili versi tidak seragam dan mesin Turing adalah hal-hal yang seragam. Saya kira "seragam" adalah cara untuk menahan kelas...
Saya tertarik pada dua pertanyaan tentang bahasa konteks-sensitif (CSL) dan kelengkapan: Apakah ada gagasan tentang kelengkapan untuk CSL, dan bahasa apa yang lengkap? Apakah ada CSL alami yang lengkap dengan NP? Untuk 2., saya pasti bisa memikirkan bahasa NP-lengkap alami yang CSL (karena...
Misalkan kita diberi n oleh n matriks, M, dengan entri bilangan bulat. Bisakah kita memutuskan di P apakah ada permutasi sehingga untuk semua permutasi kita memiliki ?σσ\sigmaπ≠σπ≠σ\pi\ne\sigmaΠMiσ(i)≠ΠMiπ(i)ΠMiσ(i)≠ΠMiπ(i)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Catatan. Seseorang tentu saja dapat...
Blum, Micali, dan Feldman (BFM) mengajukan model baru (kriptografi), di mana semua pihak (jujur atau bermusuhan) memiliki akses ke beberapa string. Tali diasumsikan dipilih berdasarkan beberapa distribusi (biasanya, distribusi seragam) oleh pihak yang dipercaya. Ini disebut string referensi , dan...
Latar belakang : Dalam kertas UGC asli Subhash Khot ( PDF ), ia membuktikan kekerasan UG memutuskan apakah contoh CSP yang diberikan dengan kendala semua bentuk Tidak-semua-sama (a, b, c) pada alfabet ternary mengakui tugas yang memuaskan 1 - ϵϵ\epsilon dari kendala atau apakah tidak ada tugas...
Nisan membuktikan dalam "Psuedorandom Generator untuk Space-Bounded Computation", bahwa ada generator pseudo-acak yang "membodohi" perhitungan yang dibatasi ruang. Apakah konstruksi ini berlaku untuk setiap oracle (setidaknya untuk permintaan
Saya mencari contoh teknik untuk membuktikan harga batas anarki yang memiliki kekuatan untuk memisahkan harga anarki atas keseimbangan berkorelasi kasar (rangkaian pembatas dinamika tanpa penyesalan eksternal) dari harga anarki atas kesetimbangan berkorelasi (pembatas set dinamika...
Saya telah memikirkan varian hex , di mana alih-alih kedua pemain membuat gerakan secara bergantian, setiap belokan yang dipilih pemain secara acak membuat gerakan. Seberapa sulit untuk menentukan peluang untuk setiap pemain yang menang? Masalah ini jelas di PSPACE, tetapi tidak bisa NP-keras,...
Grafik bebas-X adalah grafik yang tidak mengandung grafik dari X sebagai subgraf yang diinduksi. Sebuah lubang adalah siklus dengan setidaknya 4 simpul. Sebuah aneh-lubang lubang dengan jumlah ganjil simpul. Sebuah antihole adalah komplemen dari lubang. Grafik (ganjil-lubang, ganjil-antihole)...
Pertanyaan ini adalah tentang buku "Cellata automata di ruang hiperbolik: Volume 2" Oleh Maurice Margenstern, Penerbit Archives contemporaines, 2008. http://books.google.com/books?id=eEgvfic3A4kC&pg=PA125 Menurut pendapat penulis, pertanyaan P = NP tidak tepat karena dalam pengaturan...