Perbaiki bilangan bulat dan alfabet . Tentukan sebagai kumpulan semua automata kondisi terbatas pada status dengan kondisi awal 1. Kami sedang mempertimbangkan semua DFA (tidak hanya yang terhubung, minimal, atau non-degenerasi); demikian, .
Sekarang perhatikan dua string dan menentukan K ( x , y ) menjadi jumlah unsur D F A ( n ) yang menerima kedua x dan y .
Pertanyaan: Apa kompleksitas komputasi ?
Pertanyaan ini memiliki implikasi untuk pembelajaran mesin .
Sunting: Sekarang ada karunia pada pertanyaan ini, saya kira sedikit lebih tepat dalam perumusan dalam urutan. Untuk , misalkan D F A ( n ) menjadi koleksi n 2 n 2 n automata, sebagaimana didefinisikan di atas. Untuk x , y ∈ { 0 , 1 } * , mendefinisikan K n ( x , y ) menjadi jumlah automata di D F A ( n ) yang menerima kedua dan y . Pertanyaan: dapatkah K n ( x , y ) dihitung dalam waktu p o l y ( n , | x | , | y | ) ?
Jawaban:
Jadi pertanyaannya cukup singkat tetapi sangat menarik. Saya mengira bahwa inputnya adalah dalam unary, dan x dan y dalam biner (atau kita memiliki masalah, seperti yang ditunjukkan oleh jawaban Kai).n x y
Pertama-tama, jika Anda tertarik untuk mengetahui sekitar, maka Anda hanya dapat menghasilkan beberapa DFA acak dan ini akan memberi Anda (whp) perkiraan yang baik. (Aku ingin tahu apakah kelas kompleksitas ini memiliki nama.)K(x,y)
Maka mengetahui justru tampak seperti masalah yang sulit. Seperti yang ditunjukkan dalam komentar oleh a3_nm dan Kaveh, pertanyaannya setara dengan menentukan jumlah automata yang x dan y pergi ke keadaan yang sama. Saya akan menunjukkan probabilitas bahwa mereka pergi ke keadaan yang sama dengan p .K(x,y) x y p
Pembaruan: Beberapa hal yang saya tulis di sini tidak benar, sekarang saya memperbaikinya.
Sangat mudah untuk melihat bahwa . Kita memiliki persamaan, jika x adalah semua 0 dan y semua nol kecuali bit terakhirnya, yaitu 1. Apakah ada kasus lain? Saya tidak tahu Jika misalnya x adalah string kosong dan y = 00 , maka p = n + 1p≥1/n x y x y=00 .p=n+1(n−1)n
Untuk menyederhanakan masalah, saya bahkan mulai berpikir tentang apa yang terjadi jika dan y adalah unary. Jika keduanya setidaknya n dan perbedaannya dapat dibagi oleh n ! , lalu p = 1 . Apakah ada formula sederhana untuk versi unary?x y n n! p=1
sumber
Saya mungkin sangat kehilangan intinya tetapi Anda menyatakan bahwa sudah diperbaiki, sehingga semua DFA dengan ukuran itu dapat dianggap sudah dikomputasi dan disimpan dalam format yang mudah disimulasikan. Hitung K sebagai berikut:n K
Pada input , y di mana x , y ∈ Σ ∗x y x,y∈Σ∗
Sebuah. simulasikan pada kedua kata (langkah ini adalah )O(|xy|)
b. kenaikan jika kedua simulasi berjalan menerimac
Secara keseluruhan, perhitungan memiliki kompleksitas linier. Jawabannya sangat berbeda untuk .K(n,x,y)
sumber