Batas bawah untuk NFA yang menerima bahasa 3 huruf

Terkait dengan pertanyaan terbaru ( Batas pada ukuran NFA terkecil untuk L_k-berbeda ) Noam Nisan meminta metode untuk memberikan batas bawah yang lebih baik untuk ukuran NFA daripada apa yang kita dapatkan dari batas kompleksitas komunikasi. Berikut ini adalah versi khusus dari masalah itu.

Misalkan adalah bahasa lebih dari beberapa alfabet huruf yang kata-katanya memiliki panjang . Nyatakan ukuran NFA terkecil yang menerima oleh . Tentukan matriks sebagai jika dan sebaliknya . Sebutkan jumlah minimal sub-level (submatrix yang hanya berisi ) yang mencakup semua dalam matriks oleh . (Jadi adalah kompleksitas komunikasi non-deterministik dari$L$$n$$3$$L$$NFA(L)$$n\times n^2$$M$$M(a;bc)=1$$abc\in L$$0$$1$$1$$1$$M$$COV(M)$$\log(COV(M))$$M$.) Sangat mudah untuk melihat . Jika kita mendefinisikan matriks sebagai jika dan sebaliknya , maka kita juga memiliki .$NFA(L)\ge COV(M)$$N$$N(ab;c)=1$$abc\in L$$0$$NFA(L)\ge COV(N)$

Apakah ada yang$L$$NFA(L)>COV(M)+COV(N)?$

Dengan fungsi dan apa kita dapat mengikatC O V ( M ) C O V ( N ) N F A ( L ) $COV(M)$$COV(N)$$NFA(L)?$

Batas ...

Sebenarnya kita memiliki , lihat Teorema 4 dalam (Gruber & Holzer 2006). Untuk batas atas, kita memiliki , lihat Teorema 11 di kertas yang sama. N F A ( L ) ≥ C o v ( M ) + C o v ( N ) 2 C o v ( M ) + C o v ( N ) ≥ D F A ( L ) ≥ N F A ( L $NFA(L) \ge Cov(M) + Cov(N)$$2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$

... tidak dapat ditingkatkan secara substansial

Mungkin ada kesenjangan antara dan . Contoh berikut, dan bukti kesenjangan, adalah adaptasi dari contoh serupa yang menggambarkan keterbatasan protokol 2-pihak untuk membuktikan batas bawah pada kompleksitas keadaan nondeterministik dari (Hromkovič et al. 2009):C o v ( M ) + C o v ( N ) N F A ( L $Cov(M)+Cov(N)$$NFA(L)$

Kami menggunakan alfabet . Biarkan .[ n ] = {1 , 2 , … , n} L = $[n]= \{\,1,2,\ldots,n\,\}$$L=\{\,xyz\in [n]^3 \mid x=y \vee x\neq z \,\}$

Kami pertama-tama merawat . Perhatikan bahwa jika dengan , maka : dalam kasus , dan dalam hal , kami juga memiliki dan dengan demikian . Juga, jika adalah dari bentuk dengan , maka iff . Jadi kita dapat menulis , dengan dan .C o v ( M ) w = x y z y = z w ∈ L x = y w ∈ L x ≠ y x ≠ z w ∈ L w x y z y ≠ z w ∈ L x ≠ z L = L ′ ∪ L ″ L ′ = { x y z ∈ $Cov(M)$$w=xyz$$y=z$$w \in L$$x=y$$w\in L$$x\neq y$$x\neq z$$w\in L$$w$$xyz$$y\neq z$$w\in L$$x\neq z$$L = L'\cup L''$n ] 3 ∣ y = z } L ″ = $L'=\{xyz\in [n]^3 \mid y=z\}$$L''=\{\,xyz\in [n]^3 \mid y\neq z \wedge x \neq z \,\}$

Sekarang perhatikan grafik bipartit dengan , , , serta dengan , , , dan . Kemudian penutup tepi bikli untuk grafik memunculkan tudung dengan submersi monokromatik,G ′ = ( U ′ , V ′ , E ′ ) U ′ = [ n ] V ′ = { y z ∈ [ n ] 2 ∣ y = z } E ′ = U ′ × V ′ G ″ = ( U ″ , V ″ , E ″ ) U ″ = [ $G' = (U',V',E')$$U'=[n]$$V'= \{yz \in [n]^2 \mid y=z\}$$E' = U' \times V'$$G'' = (U'',V'',E'')$] V ″ = { y z ∈ [ n ] 2 ∣ y ≠ z } E ″ = { ( x , y z ) ∣ x ≠ z } G = ( U ′ ∪ U ″ , V ′ ∪ V ″ , E ′ ∪ E ″ ) G M $U''=[n]$$V''= \{ yz \in [n]^2 \mid y\neq z\}$$E'' = \{(x,yz) \mid x\neq z\}$$G = (U' \cup U'',V' \cup V'', E'\cup E'')$$G$$M$$1$

Trik kernelisasi sederhana untuk menghitung penutup tepi bikli untuk adalah dengan menempatkan simpul kembar dari ke dalam kelas kesetaraan. Kemudian kita melakukan hal yang sama pada grafik yang dihasilkan untuk simpul kembar dari . Vertikal kembar adalah mereka dengan lingkungan yang identik. Langkah ini tidak mengubah jumlah minimum bikli yang diperlukan untuk mencakup semua sisi pada grafik masing-masing.G ′ U ′ V $G'$$U'$$V'$

Langkah kernelisasi menciutkan menjadi grafik dengan dua simpul dan satu tepi. Dengan demikian, tepi dapat ditutup dengan satu bikli. Menerapkan langkah kernelisasi untuk menghasilkan grafik mahkota pada simpul , yang dimensi bipartitnya (jumlah penutup tepi bikli minimum) dikenal sebagai , di mana adalah fungsi kebalikan dari koefisien binomial tengah ( De Caen et al. 1981). Perhatikan bahwa . Jadi dimensi bipartit adalah , yang identik dengan .G ′ G ′ G ″ 2 n σ ( n ) σ σ ( n ) = O ( log n ) G 1 + σ ( n ) C o v ( M $G'$$G'$$G''$$2n$$\sigma(n)$$\sigma$$\sigma(n)=O(\log n)$$G$$1+\sigma(n)$$Cov(M)$

Sekarang pertimbangkan . Perhatikan bahwa jika dengan , maka . Jika , maka iff . Jadi kita dapat menulis dengan dan . Argumen yang hampir sama seperti di atas menghasilkan .C o v ( N ) w = x y z x = y w ∈ L x ≠ y x ∈ L x ≠ z L = L ‴ ∪ L ⁗ L ‴ = { x y z ∈ [ n ] 3 ∣ x = y } L ⁗ = { x y z ∈ [ n $Cov(N)$$w=xyz$$x=y$$w \in L$$x\neq y$$x\in L$$x\neq z$$L = L''' \cup L''''$$L'''=\{xyz\in [n]^3 \mid x=y\}$3 ∣ x ≠ y ∧ x ≠ z } C o v ( N ) = 1 + σ ( n $L''''= \{xyz\in [n]^3 \mid x\neq y \wedge x\neq z\}$$Cov(N)=1+\sigma(n)$

Ini masih memberikan batas bawah pada kompleksitas negara nondeterministic dari . Perhatikan bahwa berisi semua kata dalam bentuk dengan . Untuk setiap kata seperti memperbaiki perhitungan menerima dari NFA minimal menerima . Biarkan menyatakan status yang dicapai setelah membaca awalan , dan biarkan menyatakan keadaan yang dicapai setelah membaca awalan dari kata input . Maka semua pasangan harus berbeda. Demi kontradiksi, asumsikan untuk beberapaL L x x x x ∈ [ n ] x x x L p x x q x x x x x x ( p x , q x ) ( p x , q x ) = ( p y , q y ) x ≠ $L$$L$$xxx$$x\in[n]$$xxx$$L$$p_x$$x$$q_x$$xx$$xxx$$(p_x,q_x)$$(p_x,q_x)=(p_y,q_y)$$x\neq y$. Kemudian kita dapat membuat perhitungan penerimaan pada input , sehingga NFA dalam keadaan setelah membaca awalan , dan dalam keadaan setelah membaca awalan . Tapi string tidak di . Untuk keadaan yang diatur dari NFA, ini menunjukkan bahwa . Dengan demikian, untuk besar , kita memperoleh pemisahan antara dan(kompleksitas keadaan nondeterministik ).$xyx$$p_x=q_x$$x$$q_y=q_x$$xy$$xyx$$L$$Q$$|Q|^2 \ge n$$n$$Cov(M)+Cov(N)$$|Q|$$L$

Referensi

• Dominique de Caen, David A. Gregory, Norman J. Pullman: Peringkat Boolean dari matriks nol-satu, dalam: Cadogan, Charles C. (ed.), Konferensi Karibia ke-3 tentang Combinatorics and Computing, Departemen Matematika, Universitas the the Hindia Barat, hlm. 169–173 (1981)

• Hermann Gruber dan Markus Holzer. Menemukan Batas Bawah untuk Kompleksitas Nondeterministik Negara adalah Sulit . Laporan TR06-027, Kolokium Elektronik tentang Kompleksitas Komputasi (ECCC), Maret 2006. Versi singkat muncul di: Oscar H. Ibarra dan Zhe Dang, editor, Konferensi Internasional ke-10 tentang Perkembangan Teori Bahasa (DLT 2006), Santa Barbara (CA) , AS, volume 4036 LNCS, halaman 363-374. Springer, Juni 2006.

• Juraj Hromkovic, Holger Petersen, Georg Schnitger: Pada batas teknik kompleksitas komunikasi untuk membuktikan batas bawah pada ukuran NFA minimal . Teor Komputasi. Sci. 410 (30–32): 2972–2981 (2009)