Saya tertarik dengan sedikit generalisasi DFA. Seperti biasa kita memiliki set-negara QQQ , alfabet terbatas ΣΣ\Sigma , sebuah aksi Σ∗Σ∗\Sigma^* didefinisikan pada QQQ oleh δ:Q×Σ→Qδ:Q×Σ→Q\delta : Q\times\Sigma\rightarrow Q , dan kondisi awal q0q0q_0 ; tapi bukannya biasa set terminal, kita...
Saya menulis tesis master saya di CS dan saya bekerja dengan analisis alias. Hal yang saya tertarik adalah intraprocedural, analisis aliran must-and-alias yang sensitif untuk bahasa mirip Java. Saya mencari teks yang menggambarkan dasar-dasar dari subjek ini secara terperinci tetapi tidak dapat...
Dalam sebuah pembicaraan oleh Razborov, sebuah pernyataan kecil yang aneh diposting. Jika FACTORING sulit, maka teorema kecil Fermat tidak dapat dibuktikan dalam .S12S21S_{2}^{1} Apa itu dan mengapa bukti saat ini tidak ada di ? S 1
BPPBPP\mathsf{BPP} danZPPZPP\mathsf{ZPP} adalah dua kelas kompleksitas probabilistik dasar. BPPBPP\mathsf{BPP} adalah kelas bahasa yang diputuskan oleh algoritma Turing polinomial-waktu probabilistik di mana probabilitas algoritma mengembalikan jawaban yang salah dibatasi, yaitu probabilitas...
Mari kita mendefinisikan kelas fungsi lebih dari satu set bit. Perbaiki dua distribusi yang "cukup" berbeda satu sama lain (jika Anda suka, jarak variasional mereka setidaknya , atau yang serupa).p , q ϵnnnhal,qp,qp, qϵϵ\epsilon Sekarang setiap fungsi dalam kelas ini didefinisikan oleh kumpulan...
Dalam kompleksitas komunikasi, dugaan log-rank menyatakan hal itu cc(M)=(logrk(M))O(1)cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Di mana adalah kompleksitas komunikasi M ( x , y ) dan r k ( M ) adalah pangkat M (sebagai matriks) atas
Kelas kompleksitas didefinisikan sebagai berikut (dari Wikipedia ):SP2S2P\textrm{S}_2^\textrm{P} Bahasa adalah dalam S P 2 jika ada predikat polinomial-waktu P sedemikian rupaL.L.LSP2S2PS_2^PPPP Jika , maka ada y sedemikian rupa sehingga untuk semua z , P ( x , y , z ) = 1x ∈ Lx∈L.x \in...
Adakah kelas formula CNF alami - lebih disukai yang sebelumnya telah dipelajari dalam literatur - dengan sifat-sifat berikut:CCC adalah kasus yang mudah dari SAT, seperti misalnya Horn atau 2-CNF, yaitu, keanggotaan dalam C dapat diuji dalam waktu polinomial, dan rumus F ∈ C dapat diuji untuk...
Algoritma apa yang dapat kita gunakan untuk menemukan semua akar bilangan bulat dari polinomial dengan koefisien bilangan bulat?f( x )f(x)f(x) Saya mengamati bahwa Sage dapat menemukan akar dalam beberapa detik bahkan ketika semua koefisien sangat besar. Bagaimana itu bisa dilakukan?f( x...
Apakah ada algoritma yang dikenal untuk masalah berikut yang mengalahkan algoritma naif? Input: Sistem dari ketidaksetaraan linear m .A x ≤ bAx≤bAx \le bmmm Keluaran: Solusi yang layak jika ada.x∗∈ { 0 , 1 }nx∗∈{0,1}nx^*\in \{0,1 \}^n Asumsikan bahwa dan b memiliki entri bilangan bulat....
Apakah grafik isomorfisme (masalah keputusan) dalam ? Berikut U P adalah kelas masalah keputusan diterima oleh mesin Turing ambigu (lihat kebun binatang kompleksitas ).UP∩coUPUP∩coUP\mathsf{UP}\cap
Saya mendengar hasil perkiraan pewarnaan grafik, tetapi tidak dapat menemukan sumbernya. Hasilnya adalah: Untuk setiap konstanta terdapat cukup besar sehingga mewarnai grafik -colorable dengan warna adalah NP-hard.k k h khhhkkkkkkhkhkhk Bisakah seseorang tolong tunjukkan saya ke makalah yang...
Saya mencoba memahami kelas-kelas ini tetapi selalu bingung ... pertanyaannya adalah: Apa hubungan antara dan # P , khususnya apakah ini merupakan pertanyaan terbuka?FNPFNPFNP#P#P\#P Apa hubungan dan N P ? apakah pertanyaan ini terbuka?⊕P⊕P\oplus PNPNPNP Bagaimana dengan hubungan antara dan P F...
Seberapa sulit masalah Set Cover jika jumlah elemen dibatasi oleh beberapa fungsi (misalnya, lognlogn\log n ) di mana nnn adalah ukuran instance masalah. Secara formal, Misalkan U={e1,⋯,em}U={e1,⋯,em}\mathcal{U}=\{e_1, \cdots, e_m\} dan F={S1,⋯,Sn}F={S1,⋯,Sn}\mathcal{F} = \{S_1, \cdots, S_n\}...
Pohon rentang dari suatu grafik disebut pohon kelengkapan jika rangkaian daunnya menginduksi subgraf lengkap dalam grafik host. Diberikan grafik dan bilangan k k , apa kompleksitas memutuskan jika G berisi pohon kelengkapan dengan paling banyak k daun?GGGkkkGGGkkk Alasan untuk mengajukan...
Mengingat satu set poin di ruang Euclides dimensi, masalahnya adalah untuk menentukan apakah convex hull berisi bola Unit berpusat pada titik asal.nnnddd Apakah masalah ini dalam NP? Itu dalam co-NP karena orang dapat memberikan titik di bola di luar lambung cembung sebagai saksi dan...
Kebanyakan asisten pembuktian memiliki formalisasi konsep "himpunan terbatas". Namun, formalisasi ini sangat berbeda (walaupun orang berharap semua itu pada dasarnya setara!). Apa yang saya tidak mengerti pada saat ini adalah ruang desain yang terlibat, dan apa pro dan kontra dari setiap...
Saya memiliki masalah berikut: Input: dua set interval dan T (semua titik akhir adalah bilangan bulat). Pertanyaan: adakah bijih monoton f : S → T ?SSSTTTf: S→ Tf:S→Tf:S \to T Bijection adalah monoton wrt set masuknya order pada dan T . ∀ X ⊆ Y ∈ S , f ( X ) ⊆ f ( Y )SSSTTT∀ X⊆ Y∈ S, f ( X) ⊆ f(...
Pertimbangkan bahasa tidak kosong panjang string biner . Saya dapat menggambarkan dengan rangkaian Boolean dengan input dan satu output sedemikian rupa sehingga benar iff : ini sudah terkenal.n L C n C ( w ) w ∈ LL.LLnnnL.LLCCCnnnC( w )C(w)C(w)w ∈ Lw∈Lw \in L Namun, saya ingin mewakili dengan...
Jika kita dapat membuktikan bahwa , apakah itu menyiratkan bahwa ?L = PL.=P\mathsf{L}=\mathsf{P}N L = N PNL.=NP\mathsf{NL}=\mathsf{NP} Saya pikir itu masalahnya, tapi saya tidak bisa membuktikannya (juga untuk yang