Kompleksitas 2FA keadaan k-Clique?

Dalam bentuk sederhana:

Bisakah otomat terbatas dua arah mengenali grafik $v$ -vertex yang berisi segitiga dengan status $o(v^3)$ ?

Detail

Yang menarik di sini adalah grafik $v$ -vertex yang dikodekan menggunakan urutan tepi, masing-masing tepi menjadi sepasang simpul yang berbeda dari $\{0,1,\dots,v-1\}$ .

Misalkan adalah urutan dua arah automata terbatas (deterministik atau non-deterministik), sehingga M v mengakui k -Clique pada v grafik masukan -vertex dan memiliki s ( v ) negara. Bentuk umum dari pertanyaan itu adalah: Apakah s ( v ) = Ω ( v k ) ?$(M_v)$$M_v$$k$$v$$s(v)$$s(v) = \Omega(v^k)$

Jika dan s ( v ) ≥ v k ( v ) untuk banyak sekali v , maka NL ≠ NP. Karena kurang ambisius, maka saya menetapkan bahwa k adalah tetap, dan k = 3 adalah kasus nontrivial pertama.$k = k(v) = \omega(1)$$s(v) \ge v^{k(v)}$$v$$k$$k=3$

Latar Belakang

Finite automaton dua arah (2FA) adalah mesin Turing yang tidak memiliki ruang kerja, hanya sejumlah kondisi internal, tetapi dapat memindahkan head input read-only bolak-balik. Sebaliknya, jenis hingga otomat (1FA) yang biasa digunakan hanya memindahkan kepala input satu arah saja. Automata terbatas dapat bersifat deterministik (DFA) atau nondeterministik (NFA), serta memiliki akses satu arah atau dua arah ke inputnya.

Properti grafik adalah subset dari grafik. Biarkan Q v menyatakan v grafik -vertex dengan properti Q . Untuk setiap properti grafik Q , bahasa Q v dapat dikenali oleh 1DFA dengan paling banyak 2 v ( v - 1 ) / 2 status, dengan menggunakan keadaan untuk setiap grafik yang mungkin dan memberi label menurut Q , dan transisi antar negara berlabel tepi. Q v oleh karena itu adalah bahasa reguler untuk setiap properti $Q$$Q_v$$v$$Q$$Q$$Q_v$$2^{v(v-1)/2}$$Q$$Q_v$$Q$. Dengan teorema Myhill-Nerode ada maka sampai unik untuk isomorfisma terkecil 1DFA yang mengakui . Jika ini memiliki 2 s ( v ) negara, maka batas-batas standar blowup menghasilkan bahwa 2FA mengakui Q v memiliki setidaknya s ( v ) Ω ( 1 ) negara. Jadi pendekatan ini melalui batas blowup standar hanya menghasilkan paling banyak kuadrat dalam v batas bawah pada jumlah negara di 2FA untuk setiap Q v (bahkan ketika Q sulit atau diputuskan).$Q_v$$2^{s(v)}$$Q_v$$s(v)^{\Omega(1)}$$v$$Q_v$$Q$

-Clique adalah properti grafik yang mengandungsubgraph k -vertexlengkap. Mengenali k -Clique v dapat dilakukan oleh 1NFA yang pertama-tama tidak menentukan salah satu dari ($k$$k$$k$$_v$ potensialk-clique yangberbedauntuk dicari, dan kemudian memindai input sekali, mencari masing-masing tepi yang diperlukan untuk mengkonfirmasi klik, dan melacak tepi ini menggunakan2k(k-1)/2status untuk masing-masing klik-klik potensial yang berbeda. 1NFA tersebut memiliki ($\binom{v}{k}$$k$$2^{k(k-1)/2}$menyatakan, di mana1≤cv≤e. Ketikakdiperbaiki, ini adalahstatusΘ(vk). Mengizinkan akses dua arah ke input berpotensi memungkinkan peningkatan atas ikatan satu arah ini. Pertanyaannya kemudian memintak=$\binom{v}{k}2^{k(k-1)/2} = (c_v 2^{(k-1)/2}/k)^k.v^k$$1 \le c_v \le e$$k$$\Theta(v^k)$$k=3$ apakah 2FA dapat melakukan lebih baik dari batas atas 1FA ini.

Tambahan (2017-04-16): lihat juga pertanyaan terkait untuk waktu deterministik dan jawaban yang bagus yang mencakup algoritma yang paling dikenal . Pertanyaan saya berfokus pada ruang nondeterministik tidak seragam. Dalam konteks ini pengurangan perkalian matriks yang digunakan oleh algoritma hemat waktu lebih buruk daripada pendekatan brute-force.

Tampak bagi saya bahwa segitiga dapat dilakukan oleh 2FA dengan status O ( n 2 ) (n menjadi jumlah simpul).$A$$O(n^2)$

Untuk idenya adalah sebagai berikut:$k=3$

1. Pada fase 1, memilih beberapa edge ( i , j ) dan menyimpan ( p h a s e 1 , i , j ) dalam statusnya$A$$(i,j)$$(phase 1,i,j)$
2. Dalam fase 2 ia bergerak ke beberapa tepi bentuk atau ( m , i ) dan mengasumsikan keadaan bentuk ( p h a s e 2 , j , m $(i,m)$$(m,i)$$(phase 2,j,m)$
3. Dalam fase 3, ia memeriksa bahwa ada beberapa tepi atau ( m , j ) dan menganggap negara penerima jika menemukannya.$(j,m)$$(m,j)$

Ini sebenarnya hampir dapat dilakukan dengan cara kiri ke kanan (kemudian mungkin secara nondeterministis memutuskan untuk pergi dulu untuk ( j , m ) atau ( m , j ) dalam fase 2). Namun, jika tepi ke-2 datang dalam bentuk ( m , i ) , A perlu terlebih dahulu membaca i dan kemudian m , yaitu, satu langkah kiri diperlukan di sini.$A$$(j,m)$$(m,j)$$(m,i)$$A$$i$$m$

Ini akan menghasilkan automata dengan status untuk k -Clique untuk k > 3 dengan terlebih dahulu menebak set S dengan ukuran k - 3 dan pengujian, bahwa ia node S secara berpasangan terhubung oleh tepi dan, untuk setiap i, j, m di atas, memeriksa bahwa mereka memiliki tepi untuk semua node dalam S .$O(n^{k-1})$$k$$k>3$$S$$k-3$$S$$S$