Karakterisasi mesin dari

$SAC^i$ adalah kelas masalah keputusan yang dipecahkan oleh keluarga sirkuit kedalaman dengan fanin tanpa-batas OR dan gerbang AND-fanin terikat. Negasi hanya diperbolehkan di level input. Diketahui bahwa untuk ditutup dengan komplemen dan tidak. Juga, dan karenanya memiliki karakterisasi mesin, karena LogCFL adalah sekumpulan bahasa yang diterima oleh ruang yang dibatasi dan PDA tambahan yang dibatasi waktu polinomial. Apakah ada karakterisasi mesin yang serupa dengan untuk ? $O({\log}^i{n})$ $SAC^i$ $i \geq 1$ $SAC^0$ $SAC^1 = LogCFL$ $O({\log}n)$ $SAC^i$ $i \geq 2$

cc.complexity-theory circuit-complexity space-bounded arithmetic-circuits Siwa Kintali
sumber

Apakah dan seharusnya sama?

k

$k$

i

$i$

András Salamon

Iya. Maaf atas kesalahan ketiknya. Perbaiki sekarang.

Shiva Kintali

Jawaban:

Iya. Tinggi tumpukan. , yaitu, dengan spasi dan tinggi tumpukan; ini menyiratkan konfigurasi dan karenanya bit. Kita punya $\mathsf{SAC^1} = \mathsf{NAuxPDA}(\log n, \log n)$ $O(\log n)$ $O(\log n)$ $\log n$ $\log^2(n)$

S A C^{k} = N A u x P D A (\log n, \log^{k} n);

$\mathsf{SAC^k} = \mathsf{NAuxPDA}(\log n, \log^k n);$

mesin ini akan berjalan dalam waktu . Tanpa batasan ketinggian tumpukan, kita akan mendapatkan tepat . Hasilnya harus mengikuti dari: W. Ruzzo, bergantian seukuran pohon. JCSS 1980. $2^{\log^{k}(n)}$ $\mathsf{P}$

V Vinay
sumber

Vinay, Anda dapat menggunakan lateks biasa dalam jawabannya: mungkin membantu membuatnya sedikit lebih mudah dibaca

Suresh Venkat