Memisahkan Logspace dari waktu Polinomial

Jelas bahwa setiap masalah yang dapat ditentukan dalam deterministic logspace ( $L$ ) berjalan paling banyak waktu polinomial ( $P$ ). Ada banyak kelas kompleksitas antara $L$ dan $P$ . Contohnya termasuk $NL$ , $LogCFL$ , $NC^i$ , $SAC^i$ , $AC^i$ , $SC^i$ . Hal ini secara luas diyakini bahwa $L \neq P$ .

Dalam salah satu saya posting blog saya sebutkan dua pendekatan (bersama dengan dugaan yang sesuai) terhadap membuktikan $L \neq P$ . Kedua pendekatan ini didasarkan pada program percabangan dan terpisah 20 tahun !! Apakah ada pendekatan lain dan / atau dugaan terhadap memisahkan $L$ dari $P$ (atau) memisahkan setiap kelas menengah antara $L$ dan $P$ .

Batas bawah batas kedalaman sirkuit (ekuivalen, batas bawah ukuran rumus) mungkin merupakan pendekatan yang paling alami: Super- $\log^2(n)$ kedalaman batas bawah untuk masalah dalam $\mathsf P$ akan memisahkan $\mathsf P$ dari $\mathsf L$ , dan teknik kompleksitas komunikasi Karchmer-Wigderson mungkin jadilah yang alami untuk itu.

[1] membuktikan batas bawah untuk contoh aliran mincost yang ukuran bitnya cukup besar (tetapi masih linier) dibandingkan dengan ukuran grafik, dan selanjutnya membuktikan bahwa jika seseorang dapat menunjukkan batas bawah yang sama untuk input yang cukup kecil bit-size itu akan menyiratkan (dan karenanya P ≠ L ). Ini, pada level tinggi, sama dengan jawaban Noam dalam hal ini tentang membuktikan batas sirkuit batas bawah (= batas bawah ukuran formula), tetapi tampaknya arah yang sangat berbeda dari permainan Karchmer-Wigderson.$\mathsf{P} \neq \mathsf{NC}$$\mathsf{P} \neq \mathsf{L}$

Secara lebih rinci, [1] menunjukkan yang berikut. Menggunakan notasi yang sama seperti di kertas, misalkan menunjukkan bahasa aliran mincost. Kita dapat memikirkan bahasa aliran mincost pada grafik n -vertex, dilambangkan L ( n ) , sebagai bagian dari Z k ( n ) untuk beberapa k ( n ) = Θ ( n 2 ) , dengan bilangan bulat yang dikodekan oleh bit-string . Mari B ( a , n ) menyatakan himpunan semua vektor di Z k ( n $L$$n$$L(n)$$\mathbb{Z}^{k(n)}$$k(n) = \Theta(n^2)$$B(a,n)$$\mathbb{Z}^{k(n)}$di mana setiap bilangan bulat koordinat memiliki ukuran bit paling . Diberikan fungsi f ( x 1 , ... , x k ) (kami akan menentukan jenis fungsi apa nanti), kami mengatakan bahwa f memisahkan L ( n ) dalam B ( a , n ) jika titik dalam L ( n ) ∩ B ( a , n ) persis seperti itu → x ∈ B ( a $an$$f(x_1, \dotsc, x_k)$$f$$L(n)$$B(a,n)$$L(n) \cap B(a,n)$ sedemikian rupa sehingga f ( → x ) = 1 .$\vec{x} \in B(a,n)$$f(\vec{x}) = 1$

Proposisi [1, Proposisi 7.3] Jika dipisahkan dalam B ( a , n ) oleh det ( M ( → x ) ) di mana M adalah matriks ukuran ≤ 2 n / d yang isinya adalah kombinasi linear (kompleks) dari x 1 , ... , x k , dan sehingga sebuah < 1 / ( 2 d ) , maka P ≠ $L(n)$$B(a,n)$$\det(M(\vec{x}))$$M$$\leq 2^{n/d}$$x_1, \dotsc, x_k$$a < 1/(2d)$ .$\mathsf{P} \neq \mathsf{NC}$

Hubungan antara bit-bound dan size bound 2 n / d sangat penting di sini. Di kertas yang sama, ia menunjukkan:$an$$2^{n/d}$

Teorema [1, Teorema 7.4] Hipotesis dari proposisi sebelumnya berlaku untuk semua bit-bound yang cukup besar .$a$

Bukti teorema di atas menggunakan beberapa palu berat sebagai kotak hitam, tetapi sebaliknya elementer (catatan: "element" " mudah "). Yaitu, menggunakan Milnor-Thom terikat pada jumlah komponen yang terhubung dari varietas semialgebraic nyata (ikatan yang sama digunakan oleh Ben-Atau untuk membuktikan batas bawah pada Elemen Perbedaan / Penyortiran dalam model pohon perhitungan nyata), dekomposisi Collins ( digunakan untuk membuktikan eliminasi quantifier efektif atas R ), argumen posisi umum, dan beberapa ide lainnya. Namun, semua teknik ini hanya bergantung pada derajat polinomial yang terlibat, sehingga tidak dapat digunakan untuk membuktikan P ≠ N C seperti dalam atas Proposition (memang, [1, Prop. 7,5] membangun polinomial$\neq$$\mathbb{R}$$\mathsf{P} \neq \mathsf{NC}$ dengan derajat yang sama dengan det sehingga proposisi di atas gagal dengan g sebagai pengganti det ). Menganalisis situasi ini dan mencari properti yang melampaui derajat adalah salah satu inspirasi untuk GCT.$g$$\det$$g$$\det$

[1] K. Mulmuley. Batas Bawah dalam Model Paralel tanpa Operasi Bit . SIAM J. Comput., 28 (4), 1460–1509, 1999

Itu membuat hari saya ketika teman saya James mengatakan kepada saya bahwa utas ini sejak lama dihidupkan kembali. Terima kasih untuk itu.

Juga, saya memiliki keinginan untuk berbagi beberapa referensi menarik yang relevan dengan L vs Log (DCFL) vs Log (CFL). Semoga hari mu menyenangkan!

http://link.springer.com/chapter/10.1007%2F978-3-642-14031-0_35#page-1

http://link.springer.com/chapter/10.1007/3-540-10003-2_89?no-access=true

http://link.springer.com/chapter/10.1007%2F978-3-642-00982-2_42#page-1

http://www.researchgate.net/publication/220115950_A_Hardest_Language_Recognized_by_Two-Way_Nondeterministic_Pushdown_Automata

makalah baru ini hanya disorot oleh Luca Aceto di blog - nya sebagai makalah mahasiswa terbaik EATCS di ICALP 2014 & memiliki cara baru untuk memisahkan NL / P:

• Hasil Kekerasan untuk Persimpangan Wehar Non-Kekosongan

  $c_1$$c_2$$k$$k$$c_1 k \log(n)$$c_2 k \log(n)$$o \left( \frac{n}{\log(n) \log(\log(n))} \right)$$f(k) = o(k)$$k$$k$$n^{f(k)}$$c$$k$$k$$n^c$ waktu, maka P tidak mengandung kelas kompleksitas ruang yang lebih besar dari NL.