Dalam Lampiran B dari Meningkatkan dan Privasi Diferensial oleh Dwork et al., Penulis menyatakan hasil berikut tanpa bukti dan menyebutnya sebagai ketidaksetaraan Azuma: Biarkan C1,…,CkC1,…,CkC_1, \dots, C_k variabel acak akan bernilai real sehingga untuk setiap i∈[k]i∈[k]i \in [k] ,...
Siapa orang pertama yang menunjukkan bahwa suatu bahasa ada dalam NP jika suatu sertifikat untuk bahasa tersebut dapat diverifikasi dalam waktu polinomial? Apakah kita memiliki kertas yang secara formal membuktikan ini? Kapan komunitas TCS mulai de-menekankan non-determinisme demi verifikasi? Saya...
Saya ingin menjadi sangat spesifik. Adakah yang tahu tentang penolakan atau bukti dari proposisi berikut: ∃p∈Z[x],n,k,C∈N,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),\forall G, H \in...
Mohon maaf sebelumnya untuk pertanyaan lembut yang tidak memiliki jawaban yang benar dan tertutup. Ini mungkin forum terbaik untuk menanyakan pertanyaan saya. Saya seorang mahasiswa tahun ketiga dalam kelompok teori sekolah top-15 di AS. Sejauh ini, saya telah melakukan dengan baik. Saya memiliki...
Misalkan Anda diberi dua deterministic push down automata yang mengenali bahasa dan B , dan ingin menentukan apakah ada bahasa reguler R sehingga A ⊆ R dan R ∩ B = ∅ . Pada dasarnya, tantangannya adalah menentukan apakah ada DFA yang dapat mengenali dari dua bahasa mana string yang diberikan...
Dalam pracetak https://arxiv.org/abs/1801.00776 baru-baru ini , dinyatakan bahwa bilangan real dapat diurutkan dalam waktu O ( n √nnn dan ruang linear. Makalah ini tampaknya masuk akal, meskipun saya bukan ahli dalam menyortir algoritma.O(nlogn−−−−√),O(nlogn),O(n \sqrt{\log n}), Jika benar,...
Ada peneliti yang menunjukkan bahwa menghapus bit harus mengkonsumsi energi, sekarang adakah penelitian yang dilakukan terhadap konsumsi rata-rata algoritma dengan kompleksitas komputasi ? Saya kira, kompleksitas komputasi F ( n ) berkorelasi dengan konsumsi energi rata-rata, harap saya bisa...
Bayangkan kita memiliki dua set ukuran mmm dari titik X,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^n . Apa kerumitan (waktu) pengujian jika perbedaannya hanya berdasarkan rotasi? : ada matriks rotasi OOT=OTO=IOOT=OTO=IOO^T=O^TO=I sedemikian rupa sehingga X=OYX=OYX=OY ? Ada masalah yang mewakili nilai-nilai...
Baru-baru ini saya mencoba menerapkan Aille 's Cedille-Core , bahasa pemrograman minimalis yang mampu membuktikan teorema matematika tentang istilah-istilahnya sendiri. Saya juga telah membuktikan induksi untuk tipe data yang dikodekan dengan λ, yang menjelaskan mengapa ekstensi-nya...
Apakah ada Mesin Turing yang dapat memutuskan apakah hampir semua Mesin Turing lainnya berhenti? Misalkan kita memiliki beberapa enumerasi N→{Mi}N→{Mi}\mathbb{N} \rightarrow \{M_i\} dari mesin Turing, dan beberapa gagasan "ukuran" dari satu set bilangan alami ∥⋅∥‖⋅‖\| \cdot \| , dan kami...
Selain akademisi yang jelas merupakan rumah bagi para ahli teori, saya bertanya-tanya tentang pekerjaan industri yang berkaitan dengan ilmu komputer teoretis, yang menuntut latar belakang matematika murni. Bersulang
Pertimbangkan fungsi dihitung oleh sirkuit boolean C dengan n input ukuran s ( n ) = p o l y ( n ) atas dasar { X O R , A N D , N O T } (dengan indegree 2 untuk X O R , A N D gates).fffCCCnnns(n)=poly(n)s(n)=poly(n)s(n) =
Biarkan C4C4C_4 menjadi siklus dengan empat simpul. Untuk grafik sembarang GGG dengan nnn simpul dan tepi m, ucapkan m>nn−−√m>nnm>n\sqrt n , berapa banyakC4C4C_4yang ada? Apakah ada batas bawah untuk
Saya seorang mahasiswa pascasarjana tahun ketiga di universitas "top-20" yang bekerja pada kompleksitas berbutir halus (banyak bermain dengan 3-SUM, OV dan dugaan kekerasan populer yang biasa). Saya telah cukup produktif selama sekitar setahun terakhir dan telah menerima 3 makalah dan dua makalah...
Sudah diketahui umum bahwa komplemen bebas konteks. Tapi bagaimana dengan komplemen ?{ww∣w∈Σ∗}{ww∣w∈Σ∗}\{ ww \mid w\in \Sigma^*\}{www∣w∈Σ∗}{www∣w∈Σ∗}\{ www \mid w\in
Saya membaca buktinya dari sini dan saya menemukan masalah teknis (yang sangat penting). Saya tahu ini agak spesifik dan konteksnya bermasalah, tetapi saya sendiri tidak bisa memahaminya. Di halaman 51 dan 55, setelah menyajikan verifier "standar", mereka beralih untuk memodifikasi verifier untuk...
Asumsikan seseorang memiliki algoritma acak (BPP) AAA menggunakan rrr bit keacakan. Cara alami untuk memperbesar probabilitas keberhasilannya menjadi 1−δ1−δ1-\delta , untuk setiap δ>0δ>0\delta>0 , adalah Berjalan independen + suara terbanyak: jalankan AAA secara independen...
Saya terutama tertarik pada penggunaannya dalam aplikasi pengecekan model. Saya memiliki Jaringan Antrian Terbuka, Tertutup dan Campuran dengan Kelas Pelanggan yang Berbeda oleh Baskett et al. Ada saran lain untuk bahan bacaan? Terima
Dalam grafik yang diarahkan,G = ( V, E)G=(V,E)G=(V,E) , , jika G ∖ F adalah DAG (grafik asiklik terarah), F disebut set busur umpan balik. F⊂ EF⊂EF\subset EG ∖ FG∖FG\setminus FFFF Jika setiap sisi dikaitkan dengan bobot , masalah set busur umpan balik biaya minimum adalah untuk menemukan F...
Ketika saya memikirkan perangkat lunak yang tidak aman saya pikir itu "terlalu berguna" dan dapat disalahgunakan oleh penyerang. Jadi dalam arti mengamankan perangkat lunak adalah proses membuat perangkat lunak kurang bermanfaat. Dalam Ilmu Komputer Teoritis Anda tidak bekerja dengan dunia nyata....